This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 1e5 + 10;
ll a[maxn];
vector<pair<int,int> > t[maxn];
bool mark[maxn];
vector<ll> DP, PD;
int sz[maxn], cent;
ll dp[maxn], pd[maxn], s[maxn];
ll answer = 0;
void dfs_add(int v, int par){
PD.push_back(pd[v]);
if (dp[v] >= 0)
DP.push_back(s[v]);
for (auto edge : t[v]){
int u = edge.first;
if (u == par or mark[u])
continue;
dfs_add(u, v);
}
}
void dfs(int v, int par = -1){
if (par != -1){
if (dp[v] >= 0){
ll me = s[v];
int idx = upper_bound(PD.begin(), PD.end(), me) - PD.begin();
answer += idx;
}
int siz = DP.size();
int idx = lower_bound(DP.begin(), DP.end(), pd[v]) - DP.begin();
answer += siz - idx;
}
for (auto edge : t[v]){
int u = edge.first, w = edge.second;
if (u == par or mark[u])
continue;
s[u] = s[v] - w + a[u];
dp[u] = min(dp[v] - w + a[u], a[u] - w);
pd[u] = max(pd[v], w - (a[cent] + s[v]));
dfs(u, v);
if (par == -1){
dfs_add(u, v);
sort(DP.begin(), DP.end());
sort(PD.begin(), PD.end());
}
}
}
int dfs_sz(int v, int par = -1){
sz[v] = 1;
for (auto edge : t[v]){
int u = edge.first;
if (u != par and !mark[u])
sz[v] += dfs_sz(u, v);
}
return sz[v];
}
void centroid_decom(int v){
int Max = dfs_sz(v), par = -1;
bool found = 1;
while (found){
found = 0;
for (auto edge : t[v]){
int u = edge.first;
if (mark[u] or u == par)
continue;
if (sz[u] >= Max / 2){
par = v;
v = u;
found = 1;
break;
}
}
}
cent = v;
DP.clear();
PD.clear();
dp[v] = 0, pd[v] = 0;
s[v] = 0;
DP.push_back(s[v]);
PD.push_back(pd[v]);
dfs(v);
mark[v] = 1;
for (auto edge : t[v]){
int u = edge.first;
if (!mark[u])
centroid_decom(u);
}
}
int main(){
ios_base::sync_with_stdio(false);
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 0; i < n - 1; i++){
int v, u, w;
cin >> v >> u >> w;
t[v].push_back({u, w});
t[u].push_back({v, w});
}
centroid_decom(1);
cout << answer << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |