题意 就是给你一棵树，树边的长度为定值1，树的边长上面有权值，破坏一条边的费用就是他的权值； 求破坏一条边之后，分成两颗树A,B中直径最长的b 然后 乘上他边上的权值最小，求那条边的 id
方法 不要多说，就是保留三个最优值放在节点；两次 DFS 对树的 正向边 反方向边 赋值；最后一次性求出结果；
#pragma comment(linker, "/STACK:10240000000000,10240000000000")
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 222345
struct date{
int u,v,next,val,Max,id;
}edge[maxn];
int total,N,head[maxn],res1[maxn],res2[maxn],res3[maxn],tab1[maxn],tab2[maxn],tab3[maxn];
bool vis[maxn];
void add_edge( int u,int v,int val,int id ){
edge[total].u = u; edge[total].v = v;
edge[total].val = val; edge[total].Max = 0;
edge[total].id = id; edge[total].next = head[u];
head[u] = total++;
}
int DFS1( int sta )
{
vis[sta] = true;
for( int i = head[sta]; i != -1; i = edge[i].next )
{
int v = edge[i].v;
if( !vis[v] )
{
int t = DFS1(v) + 1; edge[i].Max = res1[v] + res2[v];
if( t >= res1[sta] )
{
res3[sta] = res2[sta]; res2[sta] = res1[sta];res1[sta] = t;
tab2[sta] = tab1[sta]; tab1[sta] = v;
}else if( t >= res2[sta] )
{
res3[sta] = res2[sta];res2[sta] = t;
tab2[sta] = v;
}else if( t > res3[sta] )res3[sta] = t;
}
}
return res1[sta];
}
void DFS2( int son,int fa,int num )
{
vis[son] = true; int t = 0; int ans = 0; int sum = 0;
if( tab1[fa] != son ){ ans += res1[fa]; sum += res1[fa];t++; }
if( tab2[fa] != son ){if(!t) ans += res2[fa]; sum += res2[fa];t++; }
if( t < 2 )sum += res3[fa];
sum = max( sum,ans+1 ); edge[num^1].Max = sum;
if( sum >= res1[son] )
{
res3[son] = res2[son]; res2[son] = res1[son];res1[son] = sum;
tab2[son] = tab1[son]; tab1[son] = fa;
}else if( sum >= res2[son] )
{
res3[son] = res2[son]; res2[son] = sum;
tab2[son] = fa;
}else if( sum > res3[son] ) res3[son] = sum;
for( int i = head[son]; i != -1; i = edge[i].next ){
int v = edge[i].v;
if( !vis[v] ) DFS2( v,son,i );
}
}
int main( )
{
int T,u,v,val,cas = 1; scanf("%d",&T);
while( T-- )
{
scanf("%d",&N); total = 0;
memset( head,-1,sizeof(head) );
for( int i = 1; i < N; i++ ){
scanf("%d%d%d",&u,&v,&val);
add_edge( u,v,val,i );
add_edge( v,u,val,i );
}
memset( vis, 0,sizeof(vis) );
memset( res1,0,sizeof(res1) );
memset( res2,0,sizeof(res2) );
memset( res3,0,sizeof(res3) );
DFS1( 1 );
memset( vis,0,sizeof(vis) ); vis[1] = true;
for( int i = head[1]; i != -1; i = edge[i].next )
DFS2( edge[i].v,1,i ); int id; int Min = (1<<30);
for( int i = 0; i < total; i += 2 )
if( edge[i].val*max(edge[i].Max,edge[i^1].Max) < Min ){
Min = edge[i].val*max( edge[i].Max,edge[i^1].Max );
id = edge[i].id;
}
printf("Case #%d: %d
",cas++,id);
}
return 0;
}
/*
2
5
4 5 1
1 5 1
2 1 1
3 5 1
5
1 4 1
1 3 1
5 1 1
2 5 1
200
20
1 2 1
2 3 1
3 4 1
3 5 1
2 6 1
6 7 1
6 8 1
2 9 1
9 10 1
1 11 1
1 12 1
12 13 1
13 14 1
13 15 1
12 16 1
16 17 1
17 18 1
12 19 1
19 20 1
*/