题目描述
X 国有 n 座城市，n - 1 条道路，每条道路连接两座城市，且任意两座城市都能通过若干条道路相互到达，显然，城市和道路形成了一棵树。
X 国现在想要将树上的两条链对应的所有道路改造成高速公路，为避免改造工程相互影响，这两条链不存在公共点。注意，链可以退化为一个点。
显然，这样会有很多个改造方案。
为评估改造方案的优劣，X 国给每条道路设定了一个重要值，注意，这里重要值越大并不代表这条路越重要。一条链的重要值为这条链上所有道路的重要值之和，当链退化为一个点时，重要值为0。
对于一个改造方案，它的优秀值为两条链的重要值之积。
你需要选择一个优秀值最大的改造方案，并求出它的优秀值。
51 nod 上原题
换根法，还要为了换根无差错，弄两次
#include#define re return#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template inline void rd(T&x){ char c;bool f=0; while((c=getchar())<'0'||c>'9')if(c=='-')f=1; x=c^48; while((c=getchar())>='0'&&c<='9')x=x*10+(c^48); if(f)x=-x;}#define ll long longconst int maxn=2e5+5;int n,m,k,hd[maxn];ll ans,d1[maxn],d0[maxn],d2[maxn],g[maxn],f[maxn];struct node{ int to,nt,val;}e[maxn<<1];inline void add(int x,int y,int z){ e[++k].to=y;e[k].nt=hd[x];hd[x]=k;e[k].val=z; e[++k].to=x;e[k].nt=hd[y];hd[y]=k;e[k].val=z;}inline void dfs(int x,int fa){ for(int i=hd[x];i;i=e[i].nt) { int v=e[i].to,w=e[i].val; if(v==fa)continue; dfs(v,x); f[x]=max(f[x],f[v]); if(d0[v]+w>d2[x]) { d2[x]=d0[v]+w; if(d2[x]>d1[x]) { swap(d2[x],d1[x]); if(d1[x]>d0[x]) swap(d0[x],d1[x]); } } } f[x]=max(f[x],d0[x]+d1[x]);}inline void rdfs(int x,int fa,ll df){ ll t0=0,t1=0; ans=max(ans,g[x]*f[x]); for(int i=hd[x];i;i=e[i].nt) { int v=e[i].to; if(f[v]>t1) { t1=f[v]; if(t1>t0) swap(t1,t0); } } for(int i=hd[x];i;i=e[i].nt) { int v=e[i].to,w=e[i].val; if(v==fa)continue; ll mx1=d0[x],mx2=d1[x],dd=df; if(d0[x]==d0[v]+w)mx1=d1[x],mx2=d2[x]; else if(d1[x]==d0[v]+w)mx2=d2[x]; dd=max(dd,mx1)+w; g[v]=max(df+mx1,max(g[fa],mx1+mx2)); rdfs(v,x,dd); }}inline void clear(){ memset(d0,0,sizeof d0); memset(d1,0,sizeof d1); memset(d2,0,sizeof d2); memset(f,0,sizeof f); memset(g,0,sizeof g);}int main(){ freopen("in.txt","r",stdin); int x,y,z; rd(n); inc(i,2,n) { rd(x),rd(y),rd(z); add(x,y,z); } dfs(n,0); rdfs(n,0,0); clear(); dfs(1,0); rdfs(1,0,0); clear(); inc(i,1,k) e[i].val=-e[i].val; dfs(n,0); rdfs(n,0,0); clear(); dfs(1,0); rdfs(1,0,0); printf("%lld",ans); re 0;}