给出一棵树，这棵树有N个点，N-1条边，正好是一个无向无环树，切去一条边，形成两棵树，使之这两棵树的最长路与切去边的权值最小，实践证明，用vector更加耗时，多了一秒，所以自己的写的链表更好
改进后的算法（耗时八百多毫秒）：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <algorithm>
using namespace std;
#pragma comment(linker,"/STACK:1024000000,1024000000")
#define N 100010
struct node
{
int v;
int index;
int next;
};
node G[N*2];
int n,p,M_A_X,_v,_u;
bool dp[N],vis[N];
int Sum[N][3], cnt[N][3],next[N],arr[N],s[N],head[N];
void add(int u,int v,int id)
{
G[p].v=v;
G[p].index=id;
G[p].next=head[u];
head[u]=p++;
}
int max_max(int x,int y)
{
return x>y?x:y;
}
void bfs(int cur,int pos)
{
queue<int> q;
q.push(cur);
dp[cur]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
if(!pos) _u=u;
else _v=u;
for(int i=head[u]; i!=-1; i=G[i].next)
{
int c=G[i].v;
if(!dp[c])
{
q.push(c),dp[c]=1;
if(pos) next[c]=u;;
}
}
}
}
void dfs(int u,int v)
{
if(dp[u]) return;
dp[u]=1;
for(int i=head[u]; i!=-1; i=G[i].next)
if(G[i].v!=v)
{
if(dp[G[i].v]) continue;
dfs(G[i].v,-1);
int m=Sum[G[i].v][1]+1;
if(Sum[u][1]<m)
{
Sum[u][2]=Sum[u][1];
Sum[u][1]=m;
}
else if(Sum[u][2]<m) Sum[u][2]=m;
Sum[u][0]=max_max(Sum[u][0],max_max(Sum[u][1]+Sum[u][2],Sum[G[i].v][0]));
}
}
void trajan(int u,int v)
{
if(dp[u]) return;
dp[u]=1;
int c;
bool flag=0;
for(int i=head[u]; i!=-1; i=G[i].next)
if(G[i].v!=v)
{
if(dp[G[i].v]) continue;
trajan(G[i].v,-1);
int m=cnt[G[i].v][1]+1;
if(cnt[u][1]<m)
{
cnt[u][2]=cnt[u][1];
cnt[u][1]=m;
}
else if(cnt[u][2]<m) cnt[u][2]=m;
cnt[u][0]=max_max(cnt[u][0],max_max(cnt[u][1]+cnt[u][2],cnt[G[i].v][0]));
}
else flag=1,c=i;
if(flag)
{
vis[G[c].index]=1;
int m=max_max(cnt[u][0],Sum[v][0])*s[G[c].index];
if(M_A_X>m||(M_A_X==m&&G[c].index<p))
{
M_A_X=m;
p=G[c].index;
}
}
}
void solve(int cur)
{
int c=0;
arr[0]=cur;
for(int v=next[cur]; v!=-1; v=next[v])
{
dfs(arr[c],v);
Sum[v][1]=Sum[arr[c]][1]+1;
Sum[v][0]=max_max(Sum[arr[c]][0],Sum[v][1]);
arr[++c]=v;
}
memset(dp,0,sizeof(bool)*(n+1));
for(int i=c-1; i>=0; --i)
{
int q=arr[i+1],v=arr[i];
trajan(q,v);
cnt[v][1]=cnt[q][1]+1;
cnt[v][0]=max_max(cnt[v][1],cnt[q][0]);
}
for(int i=1; i<n; ++i)
if(!vis[i]&&(s[i]*c<M_A_X||(s[i]*c==M_A_X&&p>i)))
{
M_A_X=s[i]*c;
p=i;
}
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("ou.txt","w",stdout);
int t,cou=1;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int u,v,w;
for(int i=0; i<=n; ++i)
{
dp[i]=vis[i]=0;
Sum[i][0]=Sum[i][1]=Sum[i][2]=0;
cnt[i][0]=cnt[i][1]=cnt[i][2]=0;
head[i]=next[i]=-1;
}
p=0;
for(int i=1; i<n; ++i)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,i);
add(v,u,i);
s[i]=w;
}
bfs(1,0);
memset(dp,0,sizeof(bool)*(n+1));
bfs(_u,1);
memset(dp,0,sizeof(bool)*(n+1));
M_A_X=0x7fffffff;
p=-1;
solve(_v);
printf("Case #%d: %d\n",cou++,p);
}
return 0;
}
以前的算法（耗时一千九百多毫秒）：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#pragma comment(linker,"/STACK:1024000000,1024000000")
struct node
{
int v;
int w;
int index;
node(int u,int x,int y)
{
v=u;
w=x;
index=y;
}
};
vector<node> G[100011];
int s[100011];
int n,p,M_A_X,_v,_u;
bool dp[100011],vis[100011];
int Sum[100011][3], cnt[100011][3],next[100011],arr[100011];
int max_max(int x,int y)
{
return x>y?x:y;
}
void bfs(int cur,int pos)
{
queue<int> q;
q.push(cur);
dp[cur]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
if(!pos) _u=u;
else _v=u;
for(int i=G[u].size()-1; i>=0; --i)
{
int c=G[u][i].v;
if(!dp[c])
{
q.push(c),dp[c]=1;
if(pos) next[c]=u;;
}
}
}
}
void dfs(int u,int v)
{
if(dp[u]) return;
dp[u]=1;
for(int i=G[u].size()-1; i>=0; --i)
if(G[u][i].v!=v)
{
if(dp[G[u][i].v]) continue;
dfs(G[u][i].v,-1);
int m=Sum[G[u][i].v][1]+1;
if(Sum[u][1]<m)
{
Sum[u][2]=Sum[u][1];
Sum[u][1]=m;
}
else if(Sum[u][2]<m) Sum[u][2]=m;
Sum[u][0]=max_max(Sum[u][0],max_max(Sum[u][1]+Sum[u][2],Sum[G[u][i].v][0]));
}
}
void trajan(int u,int v)
{
if(dp[u]) return;
dp[u]=1;
int c;
bool flag=0;
for(int i=G[u].size()-1; i>=0; --i)
if(G[u][i].v!=v)
{
if(dp[G[u][i].v]) continue;
trajan(G[u][i].v,-1);
int m=cnt[G[u][i].v][1]+1;
if(cnt[u][1]<m)
{
cnt[u][2]=cnt[u][1];
cnt[u][1]=m;
}
else if(cnt[u][2]<m) cnt[u][2]=m;
cnt[u][0]=max_max(cnt[u][0],max_max(cnt[u][1]+cnt[u][2],cnt[G[u][i].v][0]));
}
else flag=1,c=i;
if(flag)
{
vis[G[u][c].index]=1;
int m=max_max(cnt[u][0],Sum[v][0])*G[u][c].w;
if(M_A_X>m||(M_A_X==m&&G[u][c].index<p))
{
M_A_X=m;
p=G[u][c].index;
}
}
}
void solve(int cur)
{
int c=0;
arr[0]=cur;
for(int v=next[cur]; v!=-1; v=next[v])
{
dfs(arr[c],v);
Sum[v][1]=Sum[arr[c]][1]+1;
Sum[v][0]=max_max(Sum[arr[c]][0],Sum[v][1]);
arr[++c]=v;
}
memset(dp,0,sizeof(bool)*(n+1));
for(int i=c-1; i>=0; --i)
{
int q=arr[i+1],v=arr[i];
trajan(q,v);
cnt[v][1]=cnt[q][1]+1;
cnt[v][0]=max_max(cnt[v][1],cnt[q][0]);
}
for(int i=1; i<n; ++i)
if(!vis[i]&&(s[i]*c<M_A_X||(s[i]*c==M_A_X&&p>i)))
{
M_A_X=s[i]*c;
p=i;
}
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("ou.txt","w",stdout);
int t,cou=1;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int u,v,w;
for(int i=0; i<=n; ++i)
{
G[i].clear();
dp[i]=vis[i]=0;
Sum[i][0]=Sum[i][1]=Sum[i][2]=0;
cnt[i][0]=cnt[i][1]=cnt[i][2]=0;
next[i]=-1;
}
for(int i=1; i<n; ++i)
{
scanf("%d%d%d",&u,&v,&w);
G[u].push_back(node(v,w,i));
G[v].push_back(node(u,w,i));
s[i]=w;
}
bfs(1,0);
memset(dp,0,sizeof(bool)*(n+1));
bfs(_u,1);
memset(dp,0,sizeof(bool)*(n+1));
M_A_X=0x7fffffff;
p=-1;
solve(_v);
printf("Case #%d: %d\n",cou++,p);
}
return 0;
}