链接:http://acm.hdu.edu.cn/showproblem.php?pid=2196
题意:开始有一台电脑，之后添加N-1台电脑(N <= 10000).从第2行到N行有两个整数a,L，表示第i台电脑和a电脑相连，之间的连线距离为L.
要求的是每台电脑与其他电脑的距离的最大值；
思路:建图之后DFS,这样可以求出以每个点为根节点到叶子节点的最大距离；我把在以该点为根的链称为重链；
现在来考虑其他情况，同一个父节点，不在重链上的点通过父节点到该点更新该点的最大值；
注意:当该点被修改时，以其为根节点的子树的节点的值都需要修改；即递推性；只有整棵树的重链上的前面少些点是不需要修改的，不在重链上的点，显然通过重链即可更新结果；在重链上的点，如果一个节点改变，这条重链下面的点都随之改变；
细节:使用dp[u][2]来u为根节点的最大长度和次大长度。当重链最大长度不能改变时，次大长度还是需要改变的。。并且直接赋值即可(无需取max);
#include<iostream> #include<cstdio> #include<cstring> #include<string.h> #include<algorithm> #include<vector> #include<cmath> #include<stdlib.h> #include<time.h> #include<stack> #include<set> #include<map> #include<queue> using namespace std; #define rep0(i,l,r) for(int i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <= (r);i++) #define rep_0(i,r,l) for(int i = (r);i > (l);i--) #define rep_1(i,r,l) for(int i = (r);i >= (l);i--) #define MS0(a) memset(a,0,sizeof(a)) #define MS1(a) memset(a,-1,sizeof(a)) #define MSi(a) memset(a,0x3f,sizeof(a)) #define inf 0x3f3f3f3f #define lson l, m, rt << 1 #define rson m+1, r, rt << 1|1 typedef pair<int,int> PII; #define A first #define B second #define MK make_pair typedef __int64 ll; template<typename T> void read1(T &m) { T x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} m = x*f; } template<typename T> void read2(T &a,T &b){read1(a);read1(b);} template<typename T> void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);} template<typename T> void out(T a) { if(a>9) out(a/10); putchar(a%10+'0'); } #define N 10010 int dp[N][3],ans[N]; int head[N],tot; struct Edge{ int to,w,Next; Edge(){} Edge(int to,int w,int Next):to(to),w(w),Next(Next){} }e[N<<1]; inline void ins(int u,int v,int w) { e[++tot] = Edge{v,w,head[u]}; head[u] = tot; } void dfs(int u,int pre) { for(int d = head[u];d;d = e[d].Next){ int v = e[d].to; if(v == pre) continue; dfs(v,u); if(dp[u][0] <= dp[v][0] + e[d].w){ dp[u][1] = dp[u][0]; dp[u][0] = dp[v][0] + e[d].w; } else if(dp[v][0]+e[d].w > dp[u][1]) dp[u][1] = dp[v][0] + e[d].w; } } void solve(int u,int pre) { for(int d = head[u];d;d = e[d].Next){ int v = e[d].to,w = e[d].w; if(v == pre) continue; //cout<<u<<" "<<v<<" "<<dp[u][1]<<" "<<dp[u][0]<<endl; if(dp[u][1] == -1 || dp[u][0]-w != dp[v][0]) //父节点已改变或者不是重链 dp[v][0] = dp[u][0] + w,dp[v][1] = -1; else if(dp[u][0] - w == dp[v][0]){ if(dp[u][1] + w >= dp[v][0]) dp[v][0] = dp[u][1] + w,dp[v][1] = -1; else dp[v][1] = dp[u][1] + w;//**更新次大的值； } solve(v,u); } } int main() { int n; while(scanf("%d",&n) == 1){ int w,v; MS0(head);MS0(dp); tot = 0; rep1(i,2,n){ read2(v,w); ins(i,v,w);ins(v,i,w); } dfs(1,-1); solve(1,-1); rep1(i,1,n){ out(dp[i][0]); puts(""); } } return 0; }