#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Nmax = 1e5 + 5;
int n, All, scade;
int w[Nmax], A[Nmax], label[Nmax];
bool used[Nmax];
ll need_up[Nmax], need_down[Nmax], cost[Nmax], fuel[Nmax];
ll answer;
vector<ll> valA[Nmax], valB[Nmax];
vector<int> v[Nmax], c[Nmax];
void dfs(int node, int dad = 0)
{
w[node] = 1;
for(auto it : v[node])
if(it != dad && !used[it])
{
dfs(it, node);
w[node] += w[it];
}
}
pair<int,int> centroid(int node, int dad = 0)
{
int up = All - w[node];
pair<int,int> best = {All, node};
for(auto it : v[node])
if(it != dad && !used[it])
{
best = min(best, centroid(it, node));
up = max(up, w[it]);
}
best = min(best, {up, node});
return best;
}
void prec(int node, int dad)
{
if(need_up[node] <= A[node])
valA[label[node]].push_back(fuel[node] - cost[node]);
valB[label[node]].push_back(need_down[node]);
int x, cst, i;
for(i=0; i<v[node].size(); ++i)
{
x = v[node][i];
cst = c[node][i];
if(used[x] || x == dad) continue;
if(dad == 0) label[x] = i;
else label[x] = label[node];
fuel[x] = fuel[node] + A[x];
cost[x] = cost[node] + cst;
need_up[x] = max((ll)cst, need_up[node] + cst - A[node]);
need_down[x] = max(need_down[node], cost[x] - (fuel[node] - scade));
prec(x, node);
}
}
ll calc(vector<ll> &a, vector<ll> &b) /// number of pairs such that elA >= elB
{
int i = 0, j = 0;
ll ans = 0;
for(i=0; i<a.size(); ++i)
{
while(j<b.size() && a[i] >= b[j]) ++j;
ans += j;
}
return ans;
}
void solve(int node)
{
dfs(node);
All = w[node];
node = centroid(node).second;
cost[node] = 0;
fuel[node] = A[node];
need_down[node] = need_up[node] = 0;
label[node] = v[node].size();
scade = A[node];
prec(node, 0);
vector<ll> VA, VB;
int i;
for(i=0; i<=v[node].size(); ++i)
if(i == v[node].size() || !used[v[node][i]])
{
sort(valA[i].begin(), valA[i].end());
sort(valB[i].begin(), valB[i].end());
answer -= calc(valA[i], valB[i]);
for(auto it : valA[i]) VA.push_back(it);
for(auto it : valB[i]) VB.push_back(it);
valA[i].clear(); valB[i].clear();
}
sort(VA.begin(), VA.end());
sort(VB.begin(), VB.end());
answer += calc(VA, VB);
// answer --;
used[node] = 1;
for(auto it : v[node])
if(!used[it]) solve(it);
}
int main()
{
// freopen("input", "r", stdin);
cin.sync_with_stdio(false);
int i, x, y, cost;
cin >> n;
for(i=1; i<=n; ++i) cin >> A[i];
for(i=1; i<n; ++i)
{
cin >> x >> y >> cost;
v[x].push_back(y);
v[y].push_back(x);
c[x].push_back(cost);
c[y].push_back(cost);
}
solve(1);
cout << answer << '\n';
return 0;
}
Compilation message
transport.cpp: In function 'void prec(int, int)':
transport.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<v[node].size(); ++i)
~^~~~~~~~~~~~~~~
transport.cpp: In function 'll calc(std::vector<long long int>&, std::vector<long long int>&)':
transport.cpp:76:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<a.size(); ++i)
~^~~~~~~~~
transport.cpp:78:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j<b.size() && a[i] >= b[j]) ++j;
~^~~~~~~~~
transport.cpp: In function 'void solve(int)':
transport.cpp:101:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<=v[node].size(); ++i)
~^~~~~~~~~~~~~~~~
transport.cpp:102:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i == v[node].size() || !used[v[node][i]])
~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
10360 KB |
Output is correct |
| 2 |
Correct |
16 ms |
10496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
10872 KB |
Output is correct |
| 2 |
Correct |
23 ms |
11136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
146 ms |
22084 KB |
Output is correct |
| 2 |
Correct |
114 ms |
20336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
171 ms |
26148 KB |
Output is correct |
| 2 |
Correct |
219 ms |
27980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
251 ms |
32392 KB |
Output is correct |
| 2 |
Correct |
296 ms |
36464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
142 ms |
14684 KB |
Output is correct |
| 2 |
Correct |
90 ms |
14196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
139 ms |
18488 KB |
Output is correct |
| 2 |
Correct |
187 ms |
16720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
300 ms |
20068 KB |
Output is correct |
| 2 |
Correct |
267 ms |
20408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
400 ms |
23300 KB |
Output is correct |
| 2 |
Correct |
432 ms |
23404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
546 ms |
27556 KB |
Output is correct |
| 2 |
Correct |
446 ms |
25256 KB |
Output is correct |
