【题意】
给定一棵树,问对于每个点u,到树上另一个点v的最远距离
【分析】
对于每个u,最远距离要么是向子树方向的,要么是向上走到都一个父亲,再从这个父亲的位置向下走(不能走回来的方向)到的最远位置
显然我们要设计树形dp来解决这个问题,f[u]表示u子树内的最长距离,并记录一下最大的走的是哪个儿子,然后再记录一个g[u]表示次长距离
第二次树形dp算出h[u]表示这个点向上的最大距离:
考虑儿子v,如果v是最长距离那个儿子,h[v]=max(h[u],g[u])+e,如果不是最长距离的儿子,h[v]=max(h[u],f[u])+e
这个转移方程表示v的最大向上距离,要么是走到u后就向下拐,走到u的儿子里,要么就是不拐,从u那里继承答案即可
【代码】
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=10005; int head[maxn],n; struct edge { int to,nxt,v; }e[maxn<<1]; int cnt; void add(int x,int y,int z) { e[++cnt].to=y; e[cnt].nxt=head[x]; e[cnt].v=z; head[x]=cnt; } int f[maxn],g[maxn],h[maxn],hson[maxn]; void dfs1(int u,int fa) { for(int i=head[u];i;i=e[i].nxt) { int to=e[i].to; if(to==fa) continue; dfs1(to,u); if(f[to]+e[i].v>f[u]) { g[u]=max(g[u],f[u]); f[u]=f[to]+e[i].v; hson[u]=to; } else g[u]=max(g[u],f[to]+e[i].v); } } void dfs2(int u,int fa) { for(int i=head[u];i;i=e[i].nxt) { int to=e[i].to; if(to==fa) continue; if(to==hson[u]) h[to]=max(h[u],g[u])+e[i].v; else h[to]=max(h[u],f[u])+e[i].v; dfs2(to,u); } } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); while(scanf("%d",&n)!=EOF) { int x,y; memset(head,0,sizeof(head)); cnt=0; for(int i=1;i<=n;i++) f[i]=h[i]=g[i]=hson[i]=0; for(int i=2;i<=n;i++) { scanf("%d%d",&x,&y); add(i,x,y); add(x,i,y); } dfs1(1,0); dfs2(1,0); for(int i=1;i<=n;i++) printf("%d\n",max(f[i],h[i])); } return 0; }