如果不在最长路的边，那么肯定是w*最长路。
如果在最长路，那么把最长路分成两段，左边树的最长路就是左段+左边点的次短路(不包含最长路上的点的最长路) ，右边同理。
还有就是更新，经过左端点的最长路，不一定是整颗左边树的最长路，乱搞一下就可以了。我是搞成一条链，写的很麻烦。。从一点搞到了快四点。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 1000000
struct node
{
int u,v,w,next,id;
} edge[];
int t,n,first[],flag[];
int d[],in[],pre[];
int pre1[];
int pre2[];
int sp1[];
int sp2[];
int sp3[];
int sp4[];
int dp[];
int qu[];
int qv[];
int qw[];
void CL()
{
int i;
for(i = ; i <= n; i ++)
{
first[i] = -;
flag[i] = ;
dp[i] = ;
}
t = ;
}
void add(int u,int v,int w,int id)
{
edge[t].u = u;
edge[t].v = v;
edge[t].w = w;
edge[t].next = first[u];
edge[t].id = id;
first[u] = t ++;
}
void dfs(int x)
{
int i,maxz,v;
in[x] = ;
maxz = ;
for(i = first[x]; i != -; i = edge[i].next)
{
v = edge[i].v;
if(flag[v]||in[v]) continue;
in[v] = ;
dfs(v);
maxz = dp[v] + ;
}
dp[x] = maxz;
return;
}
int spfa(int x)
{
int u,v,i;
for(i = ; i <= n; i ++)
{
d[i] = -INF;
pre[i] = -;
in[i] = ;
}
queue<int>que;
que.push(x);
in[x] = ;
d[x] = ;
while(!que.empty())
{
u = que.front();
que.pop();
for(i = first[u]; i != -; i = edge[i].next)
{
v = edge[i].v;
if(in[v]) continue;
if(d[v] < d[u] + )
{
d[v] = d[u] + ;
pre[v] = u;
pre1[v] = i;
in[v] = ;
que.push(v);
}
}
}
int id,maxz = ;
for(i = ; i <= n; i ++)
{
if(maxz < d[i])
{
maxz = d[i];
id = i;
}
}
return id;
}
int main()
{
int cas,i,u,v,w,a,b,tmax,bb,aa,sn = ;
scanf("%d",&cas);
while(cas--)
{
scanf("%d",&n);
CL();
for(i = ; i < n; i ++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w,i);
add(v,u,w,i);
qu[i] = u;
qv[i] = v;
qw[i] = w;
}
b = spfa(a = spfa());
bb = b;
aa = a;
tmax = d[b];
while(b != a)
{
flag[b] = ;
pre2[pre[b]] = b;
b = pre[b];
}
flag[a] = ;
for(i = ; i <= n; i ++)
in[i] = ;
for(i = ; i <= n; i ++)
{
if(flag[i]||in[i])
{
dfs(i);
}
}
int minz = INF,num,res = -;
b = bb;
num = ;
while()
{
sp1[b] = dp[b]+tmax - num;
sp2[b] = num + dp[b];
num ++;
if(a == b) break;
b = pre[b];
}
int pos = ;
b = bb;
a = aa;
while(b != a)
{
sp2[pre[b]] = max(pos,sp2[pre[b]]);
pos = sp2[pre[b]];
b = pre[b];
}
b = bb;
a = aa;
pos = ;
while(a != b)
{
sp1[pre2[a]] = max(pos,sp1[pre2[a]]);
pos = sp1[pre2[a]];
a = pre2[a];
}
b = bb;
a = aa;
for(i = ; i < n; i ++)
{
if(flag[qu[i]]&&flag[qv[i]])
{
if(pre[qu[i]] == qv[i])
{
u = qu[i];
v = qv[i];
}
else
{
u = qv[i];
v = qu[i];
}
int tt = qw[i]*(max(sp1[v],sp2[u]));
if(minz > tt)
{
minz = tt;
res = i;
}
else if(minz == tt)
{
res = min(res,i);
}
}
else
{
if(minz > qw[i]*tmax)
{
minz = qw[i]*tmax;
res = i;
}
else if(minz == qw[i]*tmax)
{
res = min(res,i);
}
}
}
printf("Case #%d: %d\n",sn++,res);
}
return ;
}