#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100100;
vector<pair<int, int>> adj[N];
ll ans = 0;
bool vis[N];
int sz[N], m;
ll now[N], fw[N], a[N];
vector<ll> f, c;
int dfs_sz(int v, int p = -1) {
sz[v] = 1;
for (auto& [x, w] : adj[v]) {
if (x == p || vis[x]) continue;
sz[v] += dfs_sz(x, v);
}
return sz[v];
}
int centroid(int v, int p, int s) {
for (auto& [x, w] : adj[v]) {
if (x == p || vis[x]) continue;
if (sz[x] > s) return centroid(x, v, s);
}
return v;
}
void init(int v, int p, ll sum, ll d) {
if (d >= 0) ans++;
f.push_back(-d);
sum += a[v];
for (auto& [x, w] : adj[v]) {
if (x == p || vis[x]) continue;
init(x, v, sum - w, min(d, sum - w));
}
}
void add(int v, int p, ll sum, ll d) {
int idx = upper_bound(c.begin(), c.end(), -d) - c.begin();
for (int i = idx;i <= m;i += i & -i) fw[i]++;
sum += a[v];
for (auto& [x, w] : adj[v]) {
if (x == p || vis[x]) continue;
int W = a[v] - w;
add(x, v, sum - w, min(d, sum - w));
}
}
void rem(int v, int p, ll sum, ll d) {
int idx = upper_bound(c.begin(), c.end(), -d) - c.begin();
for (int i = idx;i <= m;i += i & -i) fw[i]--;
sum += a[v];
for (auto& [x, w] : adj[v]) {
if (x == p || vis[x]) continue;
rem(x, v, sum - w, min(d, sum - w));
}
}
void cal(int v, int p, ll sum, ll mn) {
if (mn >= 0) {
int idx = upper_bound(c.begin(), c.end(), sum) - c.begin();
for (int i = idx;i > 0;i -= i & -i) ans += fw[i];
}
for (auto& [x, w] : adj[v]) {
if (x == p || vis[x]) continue;
int W = a[x] - w;
cal(x, v, sum + W, min(mn + W, W));
}
}
void decom(int v) {
v = centroid(v, v, dfs_sz(v) / 2);
vis[v] = 1;
init(v, v, 0, 0);
ans--;
// compress
sort(f.begin(), f.end());
for (auto& x : f) {
if (c.empty() || x != c.back()) c.push_back(x);
}
m = c.size();
add(v, v, 0, 0);
for (auto& [x, w] : adj[v]) {
if (vis[x]) continue;
rem(x, v, a[v] - w, min(0ll, a[v] - w));
cal(x, v, a[x] - w, min(0ll, a[x] - w));
add(x, v, a[v] - w, min(0ll, a[v] - w));
}
rem(v, v, 0, 0);
f.clear();
c.clear();
for (auto& [x, w] : adj[v]) {
if (!vis[x]) decom(x);
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
for (int i = 1;i < n;i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({ v, w });
adj[v].push_back({ u, w });
}
decom(1);
cout << ans;
return 0;
}
Compilation message
transport.cpp: In function 'void add(int, int, ll, ll)':
transport.cpp:41:13: warning: unused variable 'W' [-Wunused-variable]
41 | int W = a[v] - w;
| ^
transport.cpp: In function 'void cal(int, int, ll, ll)':
transport.cpp:62:41: error: no matching function for call to 'min(ll, int&)'
62 | cal(x, v, sum + W, min(mn + W, W));
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from transport.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
230 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: template argument deduction/substitution failed:
transport.cpp:62:41: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
62 | cal(x, v, sum + W, min(mn + W, W));
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from transport.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
278 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: template argument deduction/substitution failed:
transport.cpp:62:41: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
62 | cal(x, v, sum + W, min(mn + W, W));
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from transport.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
3468 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: template argument deduction/substitution failed:
transport.cpp:62:41: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
62 | cal(x, v, sum + W, min(mn + W, W));
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from transport.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
3474 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: template argument deduction/substitution failed:
transport.cpp:62:41: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
62 | cal(x, v, sum + W, min(mn + W, W));
| ^
