題意：
有一顆樹，卻掉一條邊花費的費用為：去掉這條邊後生成的兩棵樹的最大直徑*這條邊的權值。
讓你求去掉哪條邊，花費的費用最小。輸出邊號。
做法：
可以枚舉刪掉的邊，通過記錄一些值，dp求出刪掉此邊後剩下兩棵樹
的直徑。
首先一遍dfs求出以U為根的子樹直徑f[U]，以及子樹中距離U最長的點和U的距離，和它是由U的哪個兒子得到; 同時記錄一個次大的，再記錄一個次次大的。
然後第二遍dfs，求出除去以U為根的子樹後，剩下的子樹的直徑h[U]。
如上圖：假設已經得到h[U] 了(h[ROOT] = 0)，現在要求出除去以V為根的子樹後，剩下樹的直徑h[V]，那麼h[V] 可能由四個方面得到：
1. 2中h[U]。
2. 1中U的兒子的f 最大值。
3. 1中從U的兒子出發的一條最長的鏈+2中從FA出發的一條最長鏈+2(2中從FA出發的一條最長鏈，可以單獨維護得到)。
4. 1中從U的兒子出發的一條最長的鏈+1中從U的兒子出發的一條
次長鏈+2。
代碼：
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
#define maxn 100011
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define INF 99999999
struct list
{
int u,v,w,number;
int next;
} node[maxn*4];
struct list2
{
int point;
int len;
}no[4][maxn],pp;
int head[maxn*10];
int low[maxn*2];
int f[maxn];
int ipf[maxn][2];
int ips[maxn][2];
int h[maxn];
int tops,maxx,ipos,n;
void add(int u,int v,int w,int number)
{
node[tops].u=u;
node[tops].v=v;
node[tops].w=w;
node[tops].number=number;
node[tops].next=head[u];
head[u]=tops++;
}
void init()
{
memset(head,-1,sizeof(head));
memset(f,0,sizeof(f));
memset(h,0,sizeof(h));
memset(ipf,0,sizeof(ipf));
memset(low,0,sizeof(low));
memset(ips,0,sizeof(ips));
tops=0;
maxx=INF;
ipos=maxn+10;
scanf("%d",&n);
for(int i=0;i<=n;i++)
{
no[1][i].len=no[2][i].len=no[3][i].len=0;
no[1][i].point=no[2][i].point=no[3][i].point=0;
}
int a,b,c;
for(int i=1; i<n; i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c,i);
add(b,a,c,i);
}
}
int dfs(int x,int pre)
{
int ts,tt;
ts=0;
f[x]=0;
for(int i=head[x]; i!=-1; i=node[i].next)
{
int y=node[i].v;
if(y==pre)continue;
tt=dfs(y,x)+1;
ts=max(tt,ts);
if(f[y]>=ipf[x][0])
{
ipf[x][1]=ipf[x][0];
ipf[x][0]=f[y];
ips[x][1]=ips[x][0]=y;
}
else if(f[y]>=ipf[x][1])
{
ipf[x][1]=f[y];
}
f[x]=max(f[x],f[y]);
pp.point=y;
pp.len=tt;
for(int j=1; j<=3; j++)
if(no[j][x].len<=tt)
{
for(int k=3; k>=j+1; k--)
{
no[k][x]=no[k-1][x];
}
no[j][x]=pp;
break;
}
}
int ds=no[1][x].len+no[2][x].len;
f[x]=max(f[x],ds);
return ts;
}
int chu(int pre,int x,int y)
{
int s1,s2,s3,s4;
int leap=0;
s1=s2=s3=s4=0;
if(ips[x][0]!=y)s1=ipf[x][0];
else s1=ipf[x][1];
if(no[1][x].point!=y)s2=no[1][x].len,leap++;
if(no[2][x].point!=y)s2+=no[2][x].len,leap++;
if(no[3][x].point!=y&&leap==1)s2+=no[3][x].len,leap++;
s3=h[x];
if(no[1][pre].point!=x)s4=no[1][pre].len;
else s4=no[2][pre].len;
s4=max(s4,low[pre]);
if(no[1][x].point!=y)s4+=no[1][x].len;
else s4+=no[2][x].len;
if(pre!=0)s4++;
return max(max(s1,s2),max(s3,s4));
}
void spfa(int x,int pre)
{
int visit[maxn];
memset(visit,0,sizeof(visit));
queue<int>q;
queue<int>qp;
q.push(x);
qp.push(pre);
visit[x]=1;
while(!q.empty())
{
x=q.front();
q.pop();
pre=qp.front();
qp.pop();
for(int i=head[x]; i!=-1; i=node[i].next)
{
int y=node[i].v;
if(y==pre)continue;
h[y]=chu(pre,x,y);
int ss=max(h[y],f[y])*node[i].w;
if(ss<maxx)
{
maxx=ss;
ipos=node[i].number;
}
else if(ss==maxx)ipos=min(ipos,node[i].number);
q.push(y);
qp.push(x);
}
}
}
void panlow(int x,int pre)
{
for(int i=head[x]; i!=-1; i=node[i].next)
{
int y=node[i].v;
if(y==pre)continue;
if(y!=no[1][x].point)
{
low[y]=max(no[1][x].len+1,low[x]+1);
}
else low[y]=max(no[2][x].len+1,low[x]+1);
panlow(y,x);
}
}
int main()
{
int t,T;
// freopen("in.txt","r",stdin);
scanf("%d",&T);
for(t=1; t<=T; t++)
{
init();
//cout<<"initover"<<endl;
if(dfs(1,0));
// cout<<"dfsover"<<endl;
panlow(1,0);
spfa(1,0);
printf("Case #%d: %d\n",t,ipos);
}
return 0;
}
