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
#include <cstdio>
#include <unordered_set>
#include <vector>

using std::unordered_set;
using std::vector;
typedef long long int i64;

i64 _mark = 1;
i64 next_mark() { return ++_mark; }

struct Node;
struct Edge {
  Node *target;
  i64 dist;
};

struct Node {
  vector<Edge> edges;
  i64 range;
  i64 mark;
  int id;
  Node() : mark(0) {}
} nodes[100100];

void in_range(Node *n, i64 remaining_dist, i64 marker, vector<Node *> &acc) {
  acc.push_back(n);
  n->mark = marker;
  for (Edge &e : n->edges) {
    if (e.target->mark != marker && e.dist <= remaining_dist) {
      in_range(e.target, remaining_dist - e.dist, marker, acc);
    }
  }
}

int compute(Node *node) {
  unordered_set<Node *> detonated = {};
  unordered_set<Node *> next_a = {node};
  unordered_set<Node *> next_b = {};
  unordered_set<Node *> *current = &next_a;
  unordered_set<Node *> *next = &next_b;

  while (!current->empty()) {
    for (Node *n : *current) {
      detonated.insert(n);
      vector<Node *> reached;
      in_range(n, n->range, next_mark(), reached);
      for (Node *n : reached) {
        if (detonated.find(n) == detonated.end()) {
          detonated.insert(n);
          next->insert(n);
        }
      }
    }

    current->clear();
    unordered_set<Node *>* tmp = current;
    current = next;
    next = tmp;
  }
  return detonated.size();
}

int main() {
  int N;
  scanf("%d", &N);
  for (int i = 0; i < N; ++i) {
    scanf("%lld", &nodes[i].range);
    nodes[i].id = i + 1;
  }
  for (int i = 1; i < N; ++i) {
    i64 a, b, c;
    scanf("%lld%lld%lld", &a, &b, &c);
    --a;
    --b;
    nodes[a].edges.push_back({.target = nodes + b, .dist = c});
    nodes[b].edges.push_back({.target = nodes + a, .dist = c});
  }
  for (int i = 0; i < N; ++i) {
    printf("%d ", compute(nodes + i));
  }
  printf("\n");
  return 0;
}