给定一课树，输出每个节点的到其他节点的最远距离
dp_down[i]表示从i出发到达其子节点的最大距离
dp_up[i]表示从i出发到其父节点的最大距离
我们先更新完dp_down
然后对于每个节点我们找到最大值最小值，同时把之前已经找到最大值算进入，
然后更新dp_up
最后每个节点的最远距离为 max(dp_up,dp_down)
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <string.h> #include <algorithm> #include <cmath> #include <stack> #include <queue> #include <set> #include <vector> #include <bitset> #include <map> using namespace std; typedef long long ll; typedef pair<ll, ll> pii; const ll mod = 1000000007; const ll INF = 10000000000000000LL; typedef unsigned long long ull; const int MAXN = 100000 + 10; struct Edge { int to,next; ll cost; }edge[MAXN]; int head[MAXN], tot; ll dp_down[MAXN];//从u出发到其子节点的最远距离 ll dp_up[MAXN]; //从u出发到其父节点的最远距离 void addedge(int u,int v,ll cost) { edge[tot].to = v; edge[tot].next = head[u]; edge[tot].cost = cost; head[u] = tot++; } void init() { tot = 0; memset(head, -1, sizeof head); memset(dp_down, 0, sizeof dp_down); memset(dp_up, 0, sizeof dp_up); } void dfs1(int u, int fa) { //从u出发到子节点的最大值 for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v == fa)continue; dfs1(v, u); dp_down[u] = max(dp_down[u], dp_down[v]+edge[i].cost); } } void dfs2(int u, int fa) { ll mx1 = dp_up[u], mx2 = 0,tmp; //获得从u出发到根节点的最大值与次大值，注意从u出发到父节点的值也要算 for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v == fa)continue; tmp=dp_down[v] + edge[i].cost; if (tmp >= mx1) { mx2 = mx1; mx1 = tmp; } else if (tmp>= mx2) mx2 = tmp; } for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v == fa)continue; tmp = dp_down[v] + edge[i].cost; if (tmp == mx1)dp_up[v] = mx2+edge[i].cost; else dp_up[v] = mx1+edge[i].cost; //更新节点 dfs2(v, u); } } int main() { int n; while (cin >> n) { init(); for (int i = 2; i <=n; i++) { int v; ll co; scanf("%d%lld", &v, &co); addedge(i, v, co); addedge(v, i, co); } dfs1(1, 1); dfs2(1, 1); for (int i = 1; i <= n; i++) printf("%d\n", max(dp_down[i], dp_up[i])); } }
