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
#include <bits/stdc++.h>
#define ll long long 

const int MAX_N = 1e5;
int n;
std::vector<std::pair<int, ll> > tree_list[MAX_N+3];

std::vector<int> list[MAX_N+3];
std::vector<int> t_list[MAX_N+3];
ll r[MAX_N+3];

void dfs1(int v, int f, int i, ll d) {
    if (d > r[i]) return;
    if (v != i) { list[i].push_back(v); t_list[v].push_back(i); }
    for (auto p : tree_list[v]) 
        if (p.first != f) dfs1(p.first, v, i, d + p.second);
}

bool visited[MAX_N+3];
std::stack<int> stack;
void dfs2(int v) {
    visited[v] = true;
    for (auto u : list[v]) if (!visited[u]) dfs2(u);
    stack.push(v);
}

int scc_id[MAX_N+3];
std::vector<int> SCC[MAX_N+3];
void dfs3(int v, int D) {
    visited[v] = true;
    scc_id[v] = D; SCC[D].push_back(v);
    for (auto u : t_list[v]) if (!visited[u]) dfs3(u, D);
}

std::vector<std::bitset<50000>> dp;
bool used[MAX_N+3];
int result[MAX_N+3];
void find_scc() {
    for (int i = 1; i <= n; i++) visited[i] = false;
    for (int i = 1; i <= n; i++) if (!visited[i]) dfs2(i);

    int c = -1;
    for (int i = 1; i <= n; i++) visited[i] = false;
    while (!stack.empty()) {
        int v = stack.top(); stack.pop();
        if (!visited[v]) { c++; dfs3(v, c); };
    }

    dp.resize(c+3);
    for (int i = 0; i <= c; i++) dp[i][i] = 1;

    for (int i = c; i >= 0; i--) {
        for (auto v : SCC[i]) {
            for (auto u : list[v]) {
                if (scc_id[u] != i && !used[scc_id[u]]) {
                    dp[i] |= dp[scc_id[u]];
                    used[scc_id[u]] = true;
                }
            }
        }
        for (auto v : SCC[i]) {
            for (auto u : list[v]) {
                used[scc_id[u]] = false;
            }
        }
    }

    for (int i = 0; i <= c; i++) {
        result[i] = 0;
        for (int j = 0; j <= c; j++) if (dp[i][j]) result[i] += SCC[j].size();
    }
}   

int main() {
    std::ios_base::sync_with_stdio(0); std::cin.tie(NULL);
    std::cin >> n;
    for (int i = 1; i <= n; i++) std::cin >> r[i];
    for (int i = 0; i < n-1; i++) {
        int u, v; ll x; std::cin >> u >> v >> x;
        tree_list[u].push_back({v, x});
        tree_list[v].push_back({u, x});
    }
    
    for (int i = 1; i <= n; i++) dfs1(i, i, i, 0);

    find_scc();

    for (int i = 1; i <= n; i++) std::cout << result[scc_id[i]] << " ";
    std::cout << "\n";
}