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
// 2022-4-min-miny-brut.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

constexpr int MAXN = 1e4 + 7;

long long mines[MAXN];

std::vector<std::pair<long long, int> > edges[MAXN];

bool exploded[MAXN];

bool visited[MAXN][MAXN];

int hmexploded;

void explode(int v);

void dfs2(int from, int v, long long hmleft) {
	if (visited[from][v]) {
		return;
	}
	visited[from][v] = true;
	for (auto u : edges[v]) {
		if (u.first <= hmleft && !visited[from][u.second]) {
			explode(u.second);
			dfs2(from, u.second, hmleft - u.first);
		}
	}
}

void explode(int v) {
	if (exploded[v]) {
		return;
	}
	exploded[v] = 1;
	hmexploded++;
	dfs2(v, v, mines[v]);
}

int main()
{
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);

	int n, u, v;
	long long w;
	std::cin >> n;
	for (int i = 1; i <= n; i++) {
		std::cin >> mines[i];
	}
	for (int i = 1; i < n; i++) {
		std::cin >> u >> v >> w;
		edges[u].push_back(std::make_pair(w, v));
		edges[v].push_back(std::make_pair(w, u));
	}

	for (int i = 1; i <= n; i++) {
		hmexploded = 0;
		for (int j = 0; j <= n; j++) {
			for (int k = 0; k <= n; k++) {
				visited[j][k] = 0;
			}
			exploded[j] = 0;
		}
		explode(i);
		std::cout << hmexploded << ' ';
	}
	std::cout << '\n';
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file