1 /*  2 题目大意：给n个点n-1条边的树，求删除哪条边时两个树中最大的直径与边权的乘积最小。  3 树的直径(Diameter)是指树上的最长简单路。  4 直径的求法：两遍BFS (or DFS)  5 若删除的边不是直径上的那么花费为max_len*wi  6 若删除的边是直径上的那么花费为max(dp[u][2],dp[v][2])*wi  7 */  8 #pragma comment(linker, "/STACK:16777216")  9 #include <iostream> 10 #include <cstdio> 11 #include <cstring> 12 #include <vector> 13 using namespace std; 14  15 const int maxn=100005; 16 int dep[maxn],ans[maxn],father[maxn],max_len;//ans下标对应边的编号 17 int dp[maxn][3];//j=0存i节点的到子树中的最长路，j=1存次长路，j=2存直径 18 bool vis[maxn];//标记是否为直径上的点 19 inline int max(int a,int b){return a>b?a:b;} 20 struct node 21 { 22     int id,w,v; 23     node(int id=0,int w=0,int v=0):id(id),w(w),v(v){} 24 }; 25 vector<node> f[maxn]; 26  27 void dfs_dep(int u,int pre)//找最长路 28 { 29     for(int i=0;i<f[u].size();i++) 30     { 31         int v=f[u][i].v; 32         if(v==pre) continue; 33         dep[v]=dep[u]+1; 34         father[v]=u; 35         dfs_dep(v,u); 36     } 37     return ; 38 } 39  40 void dfs(int u,int pre) 41 { 42     dp[u][0]=dp[u][1]=dp[u][2]=0; 43     for(int i=0;i<f[u].size();i++) 44     { 45         int v=f[u][i].v; 46         if(v==pre) continue; 47         dfs(v,u); 48         int temp=dp[v][0]+1; 49         if(temp>dp[u][0]) 50         { 51             dp[u][1]=dp[u][0];dp[u][0]=temp; 52         } 53         else if(temp>dp[u][1]) 54             dp[u][1]=temp; 55         dp[u][2]=max(dp[u][2],dp[v][2]);//u在子树直径边上与不再直径边上 56     } 57     dp[u][2]=max(dp[u][2],dp[u][0]+dp[u][1]);//u在子树直径中与不再直径中 58 } 59  60 void solve(int u,int pre) 61 { 62     for(int i=0;i<f[u].size();i++) 63     { 64         int v=f[u][i].v,id=f[u][i].id,w=f[u][i].w; 65         if(v==pre) continue; 66         solve(v,u); 67         //在树的直径上 68         if(vis[u] && vis[v]) 69             ans[id]=max(ans[id],w*dp[v][2]); 70         else ans[id]=w*max_len; 71     } 72 } 73  74 int main() 75 { 76     int t,i,n,icase=0,a,b,w; 77     scanf("%d",&t); 78     while(t--) 79     { 80         scanf("%d",&n); 81         for(i=1;i<=n;i++) f[i].clear(); 82         for(i=1;i<n;i++) 83         { 84             scanf("%d%d%d",&a,&b,&w); 85             f[a].push_back(node(i,w,b)); 86             f[b].push_back(node(i,w,a)); 87         } 88         int st,ed=1,temp; 89         dfs_dep(ed,-1); 90         for(i=1;i<=n;i++) 91             if(dep[ed]<dep[i]) ed=i; 92         dep[st=ed]=0; 93         dfs_dep(st,-1); 94         ed=st; 95         for(i=1;i<=n;i++) 96             if(dep[ed]<dep[i]) ed=i; 97         max_len=dep[ed]; 98         memset(vis,0,sizeof(vis)); 99         father[st]=-1;temp=ed;100         while(father[temp]!=-1)101             vis[temp]=true,temp=father[temp];102         memset(ans,0,sizeof(ans));103         dfs(st,-1);solve(st,-1);104         dfs(ed,-1);solve(ed,-1);105         temp=1;106         for(i=1;i<n;i++)107             if(ans[i]<ans[temp]) temp=i;108         printf("Case #%d: %d\n",++icase,temp);109     }110     return 0;111 }