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
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
using namespace std;

typedef long long lol;
typedef pair<lol, int> pli;
typedef pair<int, lol> pil;

int n;
vector<lol> r;
vector<vector<int> > g;
vector<vector<lol> > c;

vector<int> visited;
vector<lol> lastPower;

set<pli> byPower;
set<pil> byVertex;

void myInsert(int v, lol p) {
	if (p <= lastPower[v]) return;
	const lol LOW = -1;
	auto it = byVertex.lower_bound({ v, LOW });
	if (it != byVertex.end() && it->first == v) {
		lol pp = it->second;
		byVertex.erase(it);
		byPower.erase({ pp, v });
	}
	if (p < r[v]) p = r[v];
	byVertex.insert({ v, p });
	byPower.insert({ p, v });
	lastPower[v] = p;
}

void myErase(int v, lol p) {
	byVertex.erase({ v, p });
	byPower.erase({ p, v });
}

int solve(int src) {
	int res = 0;
	visited = vector<int>(n, 0);
	lastPower = vector<lol>(n, -1);
	byPower.clear();
	byVertex.clear();

	myInsert(src, r[src]);

	while (!byPower.empty()) {
		lol p = byPower.rbegin()->first;
		int v = byPower.rbegin()->second;
		myErase(v, p);
		if (0 == visited[v]) {
			++res;
			visited[v] = 1;
		}
		for (int i=0; i<g[v].size(); ++i) {
			int vv = g[v][i];
			lol cc = c[v][i];
			myInsert(vv, p - cc);
		}
	}

	return res;
}

int main() {
	scanf("%d", &n);
	r.resize(n);
	g.resize(n);
	c.resize(n);
	for (int i=0; i<n; ++i) scanf("%lld", &r[i]);
	for (int i=1; i<n; ++i) {
		int aa, bb;
		lol cc;
		scanf("%d%d%lld", &aa, &bb, &cc);
		--aa;
		--bb;
		g[aa].push_back(bb);
		c[aa].push_back(cc);
		g[bb].push_back(aa);
		c[bb].push_back(cc);
	}

	for (int src=0; src<n; ++src) {
		int res = solve(src);
		printf("%d%s", res, src+1 < n ? " " : "\n");
	}

	return 0;
}