1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122
|
#pragma GCC optimize(2) #pragma GCC optimize(3, "Ofast", "inline") #include<bits/stdc++.h> using namespace std;
typedef long long ll; typedef __int128 int128;
namespace FastIO { char buf[1 << 20], *p1, *p2; #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++) template<typename T> inline T read(T& x) { x = 0; int f = 1; char ch; while (!isdigit(ch = getchar())) if (ch == '-') f = -1; while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); x *= f; return x; } template<typename T, typename... Args> inline void read(T& x, Args &...x_) { read(x); read(x_...); return; } inline ll read() { ll x; read(x); return x; } inline void read(char *s) { scanf("%s", s + 1); } }; using namespace FastIO;
const int N = 1e4 + 10;
struct Edge { int to, nt, wt; Edge() {} Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {} }e[N << 1]; int hd[N], cnte; void AddEdge(int u, int v, int w) { e[++cnte] = Edge(v, hd[u], w); hd[u] = cnte; }
int n;
inline void Input() { read(n); int u, w; for(int i = 1; i < n; i++) { read(u, w); AddEdge(u, i + 1, w); AddEdge(i + 1, u, w); } }
int dis[N][2]; int cur;
inline void Dfs(int u, int fa) { for(int i = hd[u]; i ; i = e[i].nt) { int v = e[i].to; if(v == fa) continue; dis[v][cur] = dis[u][cur] + e[i].wt; Dfs(v, u); } }
inline void Work() { cur = 0; Dfs(1, 1); int mx = 0, du, dv; for(int i = 1; i <= n; i++) { if(mx < dis[i][cur]) { mx = dis[i][cur]; du = i; } dis[i][cur] = 0; } Dfs(du, du); mx = 0; for(int i = 1; i <= n; i++) { if(mx < dis[i][cur]) { mx = dis[i][cur]; dv = i; } } cur = 1; Dfs(dv, dv); for(int i = 1; i <= n; i++) { printf("%d\n", max(dis[i][0], dis[i][1])); } }
int main() { int T = 1; while(T--) { Input(); Work(); } return 0; }
|