题意：给定一棵树，求出每个点到树上所有点的最大距离。 思路： 先dfs预处理出来 考虑u这颗子树，往下走的最大值和次大值，然后每个点的最大值，来源一下面的最大值和它根节点往上走的最大值再取max，那么往上走的情况有两种例如下图： p代表u的父节点，根节点往上走的途径有两条，一条是继续往他的父节点走，就是up[j]+w[i]，还有一条就是它往下走，往下走就要判断一下往下走的最大值是否经过u这个点，如果经过了就只能用次打值来更新了，否则可以用最大值。
#include<bits/stdc++.h> using namespace std; const int N=20010; int n; int idx; int h[N],e[N],ne[N]; int d1[N]; int d2[N]; int w[N]; int up[N]; int p1[N]; void add(int a,int b,int c) { w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void dfs(int u,int fa) { for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(j==fa) continue; dfs(j,u); if(d1[j]+w[i]>d1[u]) d2[u]=d1[u],d1[u]=d1[j]+w[i],p1[u]=j; else if(d1[j]+w[i]>=d2[u]) d2[u]=d1[j]+w[i]; } } void dfs2(int u,int fa) { for(int i=h[u];~i;i=ne[i]) { // cout<<u<<' '<<fa<<endl; int j=e[i]; if(j==fa) continue; up[j]=max(up[u]+w[i],up[j]); if(p1[u]==j) up[j]=max(up[j],d2[u]+w[i]); else up[j]=max(up[j],d1[u]+w[i]); dfs2(j,u); } } int main() { while(cin >>n) { memset(h,-1,sizeof h); idx=0; for(int i=0;i<=n;i++) { d1[i]=0; d2[i]=0; up[i]=0; } for(int i=2;i<=n;i++) { int a,b,c; a=i; cin>>b>>c; add(a,b,c); add(b,a,c); } dfs(1,-1); dfs2(1,-1); // for(int i=1;i<=n;i++) // cout<<d1[i]<<' '<<d2[i]<<' '<<up[i]<<endl; for(int i=1;i<=n;i++) cout<<max(up[i],d1[i])<<endl; } }