[hdu 2196] Computer

一棵n个结点的树, 求每个点到其他点的最远距离. 多组数据. (n≤10^4) 以前以为不好写, 从没写过......实践一下. QAQ

const int N = 1e4;
struct Edge {
	int v, w;
};
vector<Edge> adj[N+1];
pair<int, int> dp[N+1];
int ans[N+1];

int dfs1(int u)
{
	dp[u].first = dp[u].second = 0;
	rep (i, 0, adj[u].size()) {
		Edge& e = adj[u][i];
		int d = dfs1(e.v) + e.w;
		if (d >= dp[u].first) {
			dp[u].second = dp[u].first;
			dp[u].first = d;
		} else if (d > dp[u].second)
			dp[u].second = d;
	}
	return dp[u].first;
}

void dfs2(int u, int d)
{
	ans[u] = max(dp[u].first, d);
	rep (i, 0, adj[u].size()) {
		Edge& e = adj[u][i];
		dfs2(e.v, e.w + max(d, dp[u].first == dp[e.v].first + e.w ? dp[u].second : dp[u].first));
	}
}

int main()
{
	int n;
	while (scanf("%d", &n) == 1) {
		rep (i, 1, n+1) adj[i].clear();
		rep (i, 2, n+1) {
			int f, w;
			scanf("%d%d", &f, &w);
			adj[f].push_back((Edge){i, w});
		}
		dfs1(1);
		dfs2(1, 0);
		rep (i, 1, n+1)
			printf("%d\n", ans[i]);
	}
	return 0;
}