《算法竞赛进阶指南》 第六章 325. 计算机

/*
325. 计算机
https://www.acwing.com/problem/content/description/327/

一所学校前一段时间买了第一台计算机（所以这台计算机的 ID 是 1）。

近年来，学校又购买了 N−1台新计算机。

每台新计算机都与之前买进的计算机中的一台建立连接。

现在请你求出第 i台计算机到距离其最远的计算机的电缆长度。

例如，上图中距离计算机 1最远的是计算机 4，
因此 S1=3；距离计算机 2最远的是计算机 4 和 5，
因此 S2=2；距离计算机 3 最远的是计算机 5，所以 S3=3；
同理，我们也得到 S4=4，S5=4。

输入格式
输入包含多测试数据。

每组测试数据第一行包含整数 N。

接下来 N−1 行，每行包含两个整数，第 i 行的第一个整数表示第 i 台电脑买入时连接的电脑编号，
第二个整数表示这次连接花费的电缆长度。

输出格式
每组测试数据输出 N行。

第 i 行输出第 i台电脑的 Si。

数据范围
1≤N≤10000
,
电缆总长度不超过109

输入样例：
5
1 1
2 1
3 1
1 1
输出样例：
3
2
3
4
4



10
1 6
2 1
1 5
1 6
4 7
2 1
1 4
6 6
7 9
10
1 7
2 10
1 9
4 2
5 10
1 2
2 3
5 3
1 7


18
24
25
21
24
28
25
22
34
34
21
28
38
26
28
38
23
31
31
28
*/


#include <iostream>
#include <cstring>
using namespace std;

const int N = 10010;

int h[N], e[2 * N], ne[2 * N], w[2 * N], idx;
int n;
int f[N][2][2], v[N];

void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void up(int u, int fa) {
	for (int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i]; int c = w[i];
		if (j == fa) continue;
		up(j, u);
		if (f[j][0][0] + c > f[u][0][0]) {
			f[u][1][0] = f[u][0][0]; f[u][1][1] = f[u][0][1];
			f[u][0][0] = f[j][0][0] + c; f[u][0][1] = j;
		}
		else if (f[j][0][0] + 1 > f[u][1][0]) {
			f[u][1][0] = f[j][0][0] + c; f[u][1][1] = j;
		}
	}
}



void down(int u, int fa) {
	for (int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i]; int c = w[i];
		if (j == fa) continue;
		if(f[u][0][1] == j)
			v[j] = max(v[u], f[u][1][0]) + c;
		else
			v[j] = max(v[u], f[u][0][0]) + c;

		down(j, u);
	}
}


int main()
{
	while (cin >> n) {
		memset(h, -1, sizeof h);
		memset(f, 0, sizeof f);
		memset(v, 0 , sizeof v);
		for (int i = 2; i <= n; i++) {
			int a, b; cin >> a >> b;
			add(i, a, b); add(a, i, b);
		}

		up(1, -1);
		down(1, -1);

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