题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4679
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
const int maxn =1e5+5;
const int mod=1e9+7;
const int INF=1e9;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意：给定一棵树，每条边上都有权重，
切断一条边后，对于每颗子树，
其权重是两点相距最远的距离，
对于每个边的选择都有一个权重就是边权*两颗子树最大权重。首先我们先选出一条直径出来，
对于不在这条直径上的边的选择，答案很明显，
那么在这条直径上的边，分割成两颗子树，
那么子树的最长路一定经过其直径的起点或者终点（结论）综上分析，我们可以分别从s和e出发进行DFS,
对于len数组，len[u]表示从起点到u的一段，从u子树延展下去的最长路是多少，
这部分可以通过树形DP完成，别忘了记录向下延展的路径编号。第二遍DFS的时候，沿着第一遍的DFS编号去扩展，
对于每条边，其以一端出发构成的最优解的部分，
是由len组成，去除要删除的那条边的len，遍历比较完后，
得到的最大权重就是该边的一部分答案。这样最后再扫描一遍就可以了。
*/
///数据域
int n,x,y,z,w[maxn];
///链式前向星
struct node{int u,nxt,w,id;
}e[maxn<<1];
int head[maxn],tot=0;
void init(){memset(head,-1,sizeof(head));tot=0;}
void add(int x,int y,int z,int d){e[tot]=node{y,head[x],z,d};head[x]=tot++;}
///求最长路
int solve(int &s,int &E)
{int vis[maxn];memset(vis,0xf,sizeof(vis));vis[1]=0;queue<int> p;p.push(1);while(!p.empty()){int tp=p.front();p.pop();for(int i=head[tp];~i;i=e[i].nxt){int v=e[i].u;if(vis[v]>vis[tp]+1){p.push(v);vis[v]=vis[tp]+1;}}}int tmp=0;for(int i=1;i<=n;i++) if(vis[i]>tmp) tmp=vis[i],s=i;memset(vis,0xf,sizeof(vis));vis[s]=0;p.push(s);while(!p.empty()){int tp=p.front();p.pop();for(int i=head[tp];~i;i=e[i].nxt){int v=e[i].u;if(vis[v]>vis[tp]+1){p.push(v);vis[v]=vis[tp]+1;}}}tmp=0;for(int i=1;i<=n;i++) if(vis[i]>tmp) tmp=vis[i],E=i;return tmp;///返回最长路径
}int dep[maxn],len[maxn],idx[maxn],son[maxn];
int L[maxn],R[maxn];void dfs(int u,int pre)
{dep[u]=dep[pre]+1;son[u]=0;len[u]=dep[u];///初始化for(int i=head[u];~i;i=e[i].nxt){int v=e[i].u;if(v==pre) continue;dfs(v,u);if(len[v]>len[u]){son[u]=v;len[u]=len[v];idx[u]=e[i].id;}}
}void dfs(int u,int pre,int deter,int id,int *a)
{if(u==0) return ;a[id]=max(a[id],deter);///更新答案int k=dep[u];for(int i=head[u];~i;i=e[i].nxt){int v=e[i].u;if(v==pre||v==son[u]) continue;k=max(k,dep[v]);}dfs(son[u],u,max(deter,k),idx[u],a);
}int main()
{int t;scanf("%d",&t);for(int ca=1;ca<=t;ca++){scanf("%d",&n);init();memset(L,-1,sizeof(L));memset(R,-1,sizeof(R));for(int i=1;i<n;i++){scanf("%d%d%d",&x,&y,&z);add(x,y,z,i),add(y,x,z,i);w[i]=z;}int s,e;///最长路的起点和终点int dis=solve(s,e);///最长路的距离dep[0]=-1;dfs(s,0);dfs(s,0,0,0,L);dep[0]=-1;dfs(e,0);dfs(e,0,0,0,R);int ans=INF,id=0,x;for(int i=1;i<n;i++){if(L[i]<0||R[i]<0) x=dis;else x=max(L[i],R[i]);if(ans>x*w[i]){ans=x*w[i];id=i;}}printf("Case #%d: %d\n",ca,id);}return 0;
}