记录编号	296058	评测结果	AAAAAAAAAA
题目名称	[CCPC2016网络预选]魔法少年和excited树	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.763 s
提交时间	2016-08-14 20:33:40	内存使用	2.89 MiB

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int kN = 1e5 + 10;

struct Edge {
	int v, cost;
};

int N;
int V[kN];
int down_0[kN], up_0[kN];
int ans_0[kN][2], ans_1[kN][2];
vector<Edge> G[kN];

void dfs1(int u, int fa) {
	down_0[u] = V[u];
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i].v, c = G[u][i].cost;
		if (v == fa) continue;
		dfs1(v, u);
		
		int dv = down_0[v] - 2 * c;
		if (dv > 0) down_0[u] += dv;
	}
}

void dfs2(int u, int fa, int cost) {
	if (fa) {
		int fv = max(up_0[fa], 0) + down_0[fa] - 2 * cost;
		if (down_0[u] - 2 * cost > 0) {
			fv -= down_0[u] - 2 * cost;
		}
		up_0[u] = fv;
	}
	
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i].v, c = G[u][i].cost;
		if (v == fa) continue;
		dfs2(v, u, c);
	}
}

void dfs3(int u, int fa) {
	int ans = down_0[u] + max(up_0[u], 0);
	ans_0[u][0] = ans;
	ans_0[u][1] = 0;
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i].v, c = G[u][i].cost;
		if (v == fa) continue;
		dfs3(v, u);
		int dv = down_0[v] - 2 * c;
		int tans = ans;
		if (dv > 0) {
			tans -= dv;
		}
		tans += ans_0[v][0] - c;
		if (up_0[v] > 0) {
			tans -= up_0[v];
		}
		
		if (tans > ans_0[u][0]) {
			ans_1[u][0] = ans_0[u][0];
			ans_1[u][1] = ans_0[u][1];
			ans_0[u][0] = tans;
			ans_0[u][1] = v;
		} else if (tans > ans_1[u][0]) {
			ans_1[u][0] = tans;
			ans_1[u][1] = v;
		}
	}
}

void dfs4(int u, int fa, int cost) {
	int ans = down_0[u] + max(up_0[u], 0);
	if (fa) {
		int dv = up_0[u];
		int tans = ans;
		if (dv > 0) {
			tans -= dv;
		}
		tans -= cost;
		if (ans_0[fa][1] != u) tans += ans_0[fa][0];
		else tans += ans_1[fa][0];
		dv = down_0[u] - 2 * cost;
		if (dv > 0) tans -= dv;
		
		if (tans > ans_0[u][0]) {
			ans_1[u][0] = ans_0[u][0];
			ans_1[u][1] = ans_0[u][1];
			ans_0[u][0] = tans;
			ans_0[u][1] = fa;
		} else if (tans > ans_1[u][0]) {
			ans_1[u][0] = tans;
			ans_1[u][1] = fa;
		}
	}
	
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i].v, c = G[u][i].cost;
		if (v == fa) continue;
		dfs4(v, u, c);
	}
}

void work() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) scanf("%d", V+i);
	for (int i = 1; i <= N - 1; i++) {
		int u, v, c; scanf("%d %d %d", &u, &v, &c);
		G[u].push_back((Edge){v, c});
		G[v].push_back((Edge){u, c});
	}
	
	dfs1(1, 0);
	dfs2(1, 0, 0);
	dfs3(1, 0);
	dfs4(1, 0, 0);
	
	for (int i = 1; i <= N; i++) {
		printf("%d\n", ans_0[i][0]);
	}
	
	memset(V, 0, sizeof(int) * (N + 5));
	memset(up_0, 0, sizeof(int) * (N + 5));
	memset(down_0, 0, sizeof(int) * (N + 5));
	memset(ans_0, 0, sizeof(int) * 2 * (N + 5));
	memset(ans_1, 0, sizeof(int) * 2 * (N + 5));
	for (int i = 0; i <= N; i++) G[i].clear();
}

int main() {
	// freopen("in.txt", "r", stdin);
	freopen("excitedtree.in", "r", stdin);
	freopen("excitedtree.out", "w", stdout);
	/*int t;
	scanf("%d", &t);
	for (int i = 1; i <= t; i++) {
		printf("Case #%d:\n", i);
		work();
	}
	*/
	work(); 
	return 0;
}