#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
using namespace std;
const int N = 1e5 + 5;
ll ans;
bool f[N];
int n, P, C, a[N];
vector < ll > s[N];
vector < pair < int , int > > v[N];
int get(int x, ll u) {
int l = 0, r = s[x].size() - 1, mid, res = 0;
while (l <= r) {
mid = (l + r) >> 1;
if (u + s[x][mid] >= 0)
res = s[x].size() - mid, r = mid - 1;
else
l = mid + 1;
}
return res;
}
int find_center(int x, int p, int &cen, int num) {
int tot = 1;
for (int i = 0; i < v[x].size(); ++i) {
int to = v[x][i].F;
if (f[to] || to == p) continue;
tot += find_center(to, x, cen, num);
}
if (cen == -1 && (2 * tot >= num || x == p)) cen = x;
return tot;
}
void fromc(int x, int p, ll recm, ll rec) {
if (recm >= 0) ++ans;
s[P].push_back(recm);
s[C].push_back(recm);
for (int i = 0; i < v[x].size(); ++i) {
ll to = v[x][i].F, cost = a[x] - v[x][i].S;
if (f[to] || to == p) continue;
fromc(to, x, min(recm, rec + cost), rec + cost);
}
}
void ansc(int x, int p, ll recm, ll rec) {
if (recm >= 0) {
ans += get(C, rec) - get(P, rec);
++ans;
}
for (int i = 0; i < v[x].size(); ++i) {
ll to = v[x][i].F, cost = a[to] - v[x][i].S;
if (f[to] || to == p) continue;
ansc(to, x, min(recm + cost, cost), rec + cost);
}
}
void Centroid(int x, int num) {
int cen = -1;
find_center(x, x, cen, num);
f[cen] = true;
C = cen;
for (int i = 0; i < v[cen].size(); ++i) {
ll to = v[cen][i].F, cost = a[cen] - v[cen][i].S; P = to;
if (f[to]) continue;
fromc(to, cen, cost, cost);
sort(s[to].begin(), s[to].end());
}
sort(s[cen].begin(), s[cen].end());
for (int i = 0; i < v[cen].size(); ++i) {
ll to = v[cen][i].F, cost = a[to] - v[cen][i].S; P = to;
if (f[to]) continue;
ansc(to, cen, cost, cost);
}
s[cen].clear();
for (int i = 0; i < v[cen].size(); ++i) {
int to = v[cen][i].F;
if (f[to]) continue;
s[to].clear();
Centroid(to, num / 2);
}
}
main () {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i < n; ++i) {
int a, b, c;
cin >> a >> b >> c;
v[a].pb({b, c});
v[b].pb({a, c});
}
Centroid(1, n);
cout << ans << "\n";
}
Compilation message
transport.cpp: In function 'int find_center(int, int, int&, int)':
transport.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for (int i = 0; i < v[x].size(); ++i) {
| ~~^~~~~~~~~~~~~
transport.cpp: In function 'void fromc(int, int, long long int, long long int)':
transport.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for (int i = 0; i < v[x].size(); ++i) {
| ~~^~~~~~~~~~~~~
transport.cpp: In function 'void ansc(int, int, long long int, long long int)':
transport.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for (int i = 0; i < v[x].size(); ++i) {
| ~~^~~~~~~~~~~~~
transport.cpp: In function 'void Centroid(int, int)':
transport.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (int i = 0; i < v[cen].size(); ++i) {
| ~~^~~~~~~~~~~~~~~
transport.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for (int i = 0; i < v[cen].size(); ++i) {
| ~~^~~~~~~~~~~~~~~
transport.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (int i = 0; i < v[cen].size(); ++i) {
| ~~^~~~~~~~~~~~~~~
transport.cpp: At global scope:
transport.cpp:92:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
92 | main () {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
5740 KB |
Output is correct |
| 2 |
Correct |
9 ms |
5612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
6252 KB |
Output is correct |
| 2 |
Correct |
13 ms |
7020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
93 ms |
22884 KB |
Output is correct |
| 2 |
Correct |
84 ms |
22756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
26980 KB |
Output is correct |
| 2 |
Correct |
153 ms |
35292 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
181 ms |
40668 KB |
Output is correct |
| 2 |
Correct |
232 ms |
48780 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
82 ms |
12184 KB |
Output is correct |
| 2 |
Correct |
46 ms |
8376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
116 ms |
11236 KB |
Output is correct |
| 2 |
Correct |
130 ms |
16400 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
230 ms |
16868 KB |
Output is correct |
| 2 |
Correct |
194 ms |
15572 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
336 ms |
21348 KB |
Output is correct |
| 2 |
Correct |
284 ms |
19164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
352 ms |
36196 KB |
Output is correct |
| 2 |
Correct |
342 ms |
33628 KB |
Output is correct |
