解题思路：
求出树的直径的两个端点，，则树上每个节点到其他点的最远距离一定是到这两个端点的距离中最长的那一个。
#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <cmath>#include <vector>#include <queue>#define LL long longusing namespace std;const int MAXN = 100000 + 10;struct Edge{int to, next, w;}edge[2 * MAXN];int tot;int head[MAXN];int dis[MAXN];int N, M;int D[MAXN];void init(){tot = 0;memset(head, -1, sizeof(head));memset(D, 0, sizeof(D));}void addedge(int u, int v, int w){edge[tot].to = v;edge[tot].next = head[u];edge[tot].w = w;head[u] = tot++;}int dfs(int u, int pre = -1){int ans = u;for(int i=head[u];i!=-1;i=edge[i].next){int v = edge[i].to;if(v == pre) continue;dis[v] = dis[u] + edge[i].w;int dv = dfs(v, u);if(dis[ans] < dis[dv]) ans = dv;}return ans;}int solve(int u){dis[u] = 0;u = dfs(u);dis[u] = 0;int v = dfs(u);for(int i=1;i<=N;i++) D[i] = max(D[i], dis[i]);dis[v] = 0;dfs(v);for(int i=1;i<=N;i++) D[i] = max(D[i], dis[i]);for(int i=1;i<=N;i++) cout << D[i] << endl;}int main(){while(scanf("%d", &N)!=EOF){int v, w;init();for(int i=2;i<=N;i++){scanf("%d%d", &v, &w);addedge(i, v, w);addedge(v, i, w);}solve(1);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
而只有在充满了艰辛的人生旅途中，
