题目链接：hdu 4679 Terrorist’s destroy
题意：
给一棵树，每条边上都有一个权值，去掉树上任意一条边之后，分成两个子树，两个子树的最长路与这条边上的权值相乘，的到一个乘积。问去掉那一条边可以使这个乘积最小。
题解：
首先我们先找到整棵树的直径（即最长的那条路）。
那么删边的时候有两种情况：
1. 这条边不是直径上的边。
2. 这条边是直径上的边。
对于第一种情况，直接用直径来乘就行了。
对于第二种情况，这样可以发现一个性质：两棵子树的最长路，一定是以整棵树的最长路的两个端点为起点的。然后O(n)预处理一下。
最后从直径的一个端点开始删边，然后更新答案。
1 #include<bits/stdc++.h> 2 #define mst(a,b) memset(a,b,sizeof(a)) 3 #define F(i,a,b) for(int i=a;i<=b;++i) 4 using namespace std; 5 6 const int N=1e5+7; 7 int cas,n,ans,mi,mxlen,s,t,ds[N],dt[N],ms[N],mt[N]; 8 int g[N],v[N*2],nxt[N*2],idx[N*2],w[N*2],ed; 9 void adg(int x,int y,int z,int i){v[++ed]=y,w[ed]=z,idx[ed]=i,nxt[ed]=g[x],g[x]=ed;} 10 11 inline void up(int &a,int b){if(a<b)a=b;} 12 13 void dfs(int x,int fa,int dep,int *dis) 14 { 15 dis[x]=dep; 16 for(int i=g[x];i;i=nxt[i]) 17 if(v[i]!=fa) 18 dfs(v[i],x,dep+1,dis); 19 } 20 21 void dfs2(int x,int fa,int *mx,int *dis) 22 { 23 mx[x]=dis[x]; 24 for(int i=g[x];i;i=nxt[i]) 25 if(v[i]!=fa) 26 dfs2(v[i],x,mx,dis),up(mx[x],mx[v[i]]); 27 } 28 29 void find(int x,int fa) 30 { 31 for(int i=g[x];i;i=nxt[i]) 32 if(v[i]!=fa) 33 { 34 int cost=(ds[x]+dt[v[i]]+1==mxlen?w[i]*max(ms[x],mt[v[i]]):w[i]*mxlen); 35 if(cost<mi)ans=idx[i],mi=cost; 36 else if(cost==mi&&idx[i]<ans)ans=idx[i]; 37 find(v[i],x); 38 } 39 } 40 41 int main(){ 42 scanf("%d",&cas); 43 F(ic,1,cas) 44 { 45 mst(g,0),ed=0; 46 scanf("%d",&n); 47 F(i,1,n-1) 48 { 49 int x,y,z; 50 scanf("%d%d%d",&x,&y,&z); 51 adg(x,y,z,i),adg(y,x,z,i); 52 } 53 dfs(1,0,0,ds); 54 int tmp=0; 55 F(i,1,n)if(ds[i]>tmp)s=i,tmp=ds[i]; 56 dfs(s,0,0,ds),tmp=0; 57 F(i,1,n)if(ds[i]>tmp)t=i,tmp=ds[i];//找到树的直径 58 dfs(t,0,0,dt),dfs2(s,0,mt,dt),dfs2(t,0,ms,ds);//预处理断掉该节点的一条边后最长的子树直径 59 mi=INT_MAX,mxlen=tmp; 60 find(s,0); 61 printf("Case #%d: %d ",ic,ans); 62 } 63 return 0; 64 }