记录编号	602584	评测结果	AAAAAAAAAA
题目名称	2999.[HDOJ 2196]计算机	最终得分	100
用户昵称	OTTF	是否通过	通过
代码语言	C++	运行时间	0.218 s
提交时间	2025-07-04 16:45:24	内存使用	9.23 MiB

#include <algorithm>
#include <cstring>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

int n;
vector<pair<int, long long>> tree[114514];
int father[114514];
long long dp[114514][3];

void dfs (int now, int dad) {
	for (auto [son, w] : tree[now]) {
		if (son == dad) {
			continue;
		}
		dfs (son, now);
		long long dis = dp[son][0] + w;
		if (dp[now][0] <= dis) {
			dp[now][1] = dp[now][0];
			dp[now][0] = dis;
		}
		else {
			dp[now][1] = max (dp[now][1], dis);
		}
	}
}

void doDp (int now, int dad) {
	for (auto [son, w] : tree[now]) {
		if (son == dad) {
			continue;
		}
		if (dp[now][0] == w + dp[son][0]) {
			dp[son][2] = max (dp[now][2], dp[now][1]) + w;
		}
		else {
			dp[son][2] = max (dp[now][2], dp[now][0]) + w;
		}
		doDp (son, now);
	}
}

int main () {
	
	while (cin >> n) {
		for (int i = 1; i <= n; i++) {
			tree[i].clear();
		}
		memset (dp, 0, sizeof (dp));
		long long w;
		for (int i = 2; i <= n; i++) {
			cin >> father[i] >> w;
			tree[father[i]].emplace_back(i, w);
			tree[i].emplace_back(father[i], w);
		}

		dfs (1, 0);
		doDp (1, 0);

		for (int i = 1; i <= n; i++) {
			cout << max (dp[i][0], dp[i][2]) << endl;
		}
	}
	
	
	return 0;
}