链接：http://acm.hdu.edu.cn/showproblem.php?pid=4679
题意：给定一颗树，每条边有一个权值w,问切掉哪条边之后，分成的两颗树的较大的直径*切掉边的权值最小？如果存在多条边使得结果相同，输出边id最小的
思路:
dept一次找出最深的节点，之后以最深的节点出发（rt1）dept找到树的直径（即找到rt2）；将路径保存在f[]中；
之后分别从rt1/rt2进行深搜，找到以一个节点为根的树的直径，这样在每次dfs之后，可以求出每条边的一边的最值，这样两次取max之后就求出了切掉该边之后得到的结果
注：
如果改变在整棵树的直径上，需要取出以该棵树为根的树的直径maxn[0][v];否则就直接取整棵树的直径即可；
在dfs递推出以某根为子树的直径时，可能直径不过根节点所以要将子子树的直径递推到子树上；
#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:1024000000,1024000000") //加栈
using namespace std;
#define rep0(i,l,r) for(int i = (l);i < (r);i++)
#define rep1(i,l,r) for(int i = (l);i <= (r);i++)
#define rep_0(i,r,l) for(int i = (r);i > (l);i--)
#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
#define MSi(a) memset(a,0x3f,sizeof(a))
#define inf 0x3f3f3f3f
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1|1
typedef pair<int,int> PII;
#define A first
#define B second
#define MK make_pair
typedef long long ll;
typedef unsigned int uint;
template<typename T>
void read1(T &m)
{
T x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
m = x*f;
}
template<typename T>
void read2(T &a,T &b){read1(a);read1(b);}
template<typename T>
void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}
template<typename T>
void out(T a)
{
if(a>) out(a/);
putchar(a%+'');
}
#define N 100007
int head[N<<],tot;
struct edge{
int to,w,id,Next;
}e[N<<];
void ins(int a,int b,int w,int id)
{
e[++tot].Next = head[a];
e[tot].to = b;
e[tot].w = w;
e[tot].id = id;
head[a] = tot;
}
int dep[N],p[N];
void dept(int u,int pre)
{
p[u] = pre;
dep[u] = dep[pre] + ;
for(int id = head[u];id;id = e[id].Next){
int v = e[id].to;
if(v == pre) continue;
dept(v,u);
}
}
int f[N],maxlen;//树的直径
int aux[N];
int maxn[][N];
void dfs(int u,int pre)
{
maxn[][u] = maxn[][u] = maxn[][u] = ;
for(int id = head[u];id;id = e[id].Next){
int v = e[id].to;
if(v == pre) continue;
dfs(v,u);
if(maxn[][u] <= maxn[][v]+){
maxn[][u] = maxn[][u];
maxn[][u] = maxn[][v]+;
}else if(maxn[][u] < maxn[][v]+)
maxn[][u] = maxn[][v]+;
if(maxn[][u] < maxn[][v]) //**可能树的直径不过根节点;
maxn[][u] = maxn[][v];
}
maxn[][u] = max(maxn[][u],maxn[][u] + maxn[][u]); //以u为根的子树的直径
}
void solve(int u,int pre)
{
for(int id = head[u];id;id = e[id].Next){
int v = e[id].to, w = e[id].w;
if(v == pre) continue;
if(f[u] && f[v]){ //边在直径上
aux[e[id].id] = max(aux[e[id].id],w*maxn[][v]);
}else{
aux[e[id].id] = max(aux[e[id].id],w*maxlen);
}
solve(v,u);
}
}
int main()
{
//freopen("data.txt","r",stdin);
//freopen("out.txt","w",stdout);
int kase = ,T,n;
read1(T);
while(T--){
MS0(head);tot = ;
MS0(f);
read1(n);
rep0(i,,n){
int u,v,w;
read3(u,v,w);
ins(u,v,w,i);ins(v,u,w,i);
}
dep[] = ;
dept(,);
int rt1 ,rt2 ,d = ;
rep1(i,,n) if(d < dep[i]) d = dep[i],rt1 = i;
dept(rt1,);
d = ;
rep1(i,,n) if(d < dep[i]) d = dep[i],rt2 = i;
maxlen = d-; //求出树的直径；以及两端的节点标号
int index = rt2;
while(index){
f[index] = ;
index = p[index]; //从树直径的终点递推到起点
}
MS0(aux);
dfs(rt1,-);
solve(rt1,);
dfs(rt2,-);
solve(rt2,);
int ans = inf;
rep0(i,,n){
if(ans > aux[i]) ans = aux[i],index = i;
}
printf("Case #%d: %d\n",kase++,index);
}
return ;
}