#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int maxn = 1e5;
std::vector<pair<int,i64>> graph[maxn+2];
int a[maxn+2] , n;
i64 BIT[maxn+2];
void upd(int pos , int val)
{
for (; pos <= maxn; pos += pos&-pos)
BIT[pos] += val;
return;
}
i64 get(int id)
{
i64 sum = 0;
for (; id ; id -= id&-id)
sum += BIT[id];
return sum;
}
i64 sum_range(int l , int r)
{
return get(r) - get(l-1);
}
int sub[maxn+2] ;
bool mark[maxn+2];
std::vector<pair<i64,int>> cost;
std::vector<i64> down;
int id[maxn+2];
i64 answer = 0;
int get_centroid(int v , int p , int half)
{
for (auto& [to,w] : graph[v])
{
if (mark[to] || to == p) continue;
if (sub[to] > half) return get_centroid(to,v,half);
}
return v;
}
void dfssize(int v , int p)
{
sub[v]=1;
for (auto& [to,w] : graph[v])
{
if (to==p||mark[to]) continue;
dfssize(to,v);
sub[v]+=sub[to];
}
return;
}
void downforces(int v , int p , i64 mn , i64 used)
{
down.push_back(mn);
for (auto& [to , w] : graph[v])
{
if (mark[to] || to == p) continue;
downforces(to , v , min({mn , used + a[v] - w }) , used + a[v] - w);
}
return;
}
void build(int v , int p , i64 sum )
{
if (sum >= 0)
cost.push_back({sum , v});
for (auto& [to , w] : graph[v])
{
if (to==p || mark[to]) continue;
build(to , v , sum + a[to] - w);
}
return;
}
void centroid(int v)
{
dfssize(v,v);
v = get_centroid(v,v,sub[v]/2);
mark[v] = true;
// DP
for (auto& [to,w] : graph[v])
{
if (mark[to]) continue;
build(to , v , a[to] - w);
}
vector<i64> allcost ;
std::sort(cost.begin() , cost.end());
for (int i = 0; i < cost.size(); ++i)
{
id[cost[i].second] = i + 1;
upd(id[cost[i].second] , 1);
allcost.push_back(cost[i].first);
++answer;
}
cost.clear();
for (auto& [to , w] : graph[v])
{
if (mark[to]) continue;
build(to , v , a[to] - w);
for (auto& [x,y] : cost) upd(id[y] , -1);
downforces(to , v , a[v] - w , a[v] - w);
for (auto& x : down)
{
if (x >= 0) ++answer;
int pos = lower_bound(allcost.begin() , allcost.end() , -x) - allcost.begin() ;
if (pos != allcost.size())
{
++pos;
answer += sum_range(pos , allcost.size());
}
}
down.clear();
for (auto& [x,y] : cost) upd(id[y] , 1);
cost.clear();
}
for (int i = 0; i < allcost.size(); ++i) upd(i + 1 , -1);
for (auto& [to , w] : graph[v])
if (!mark[to]) centroid(to);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n ;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 2; i <= n; ++i)
{
int u , v , w; cin >> u >> v >> w;
graph[u].push_back({v , w});
graph[v].push_back({u , w});
}
centroid(1);
cout << answer;
}
Compilation message
transport.cpp: In function 'int get_centroid(int, int, int)':
transport.cpp:37:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
37 | for (auto& [to,w] : graph[v])
| ^
transport.cpp: In function 'void dfssize(int, int)':
transport.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
48 | for (auto& [to,w] : graph[v])
| ^
transport.cpp: In function 'void downforces(int, int, i64, i64)':
transport.cpp:60:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
60 | for (auto& [to , w] : graph[v])
| ^
transport.cpp: In function 'void build(int, int, i64)':
transport.cpp:72:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
72 | for (auto& [to , w] : graph[v])
| ^
transport.cpp: In function 'void centroid(int)':
transport.cpp:86:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
86 | for (auto& [to,w] : graph[v])
| ^
transport.cpp:94:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for (int i = 0; i < cost.size(); ++i)
| ~~^~~~~~~~~~~~~
transport.cpp:103:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
103 | for (auto& [to , w] : graph[v])
| ^
transport.cpp:107:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
107 | for (auto& [x,y] : cost) upd(id[y] , -1);
| ^
transport.cpp:113:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | if (pos != allcost.size())
| ~~~~^~~~~~~~~~~~~~~~~
transport.cpp:120:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
120 | for (auto& [x,y] : cost) upd(id[y] , 1);
| ^
transport.cpp:123:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | for (int i = 0; i < allcost.size(); ++i) upd(i + 1 , -1);
| ~~^~~~~~~~~~~~~~~~
transport.cpp:125:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
125 | for (auto& [to , w] : graph[v])
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
11348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
13772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
164 ms |
17088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
7132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
8332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
9492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
127 ms |
11256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
225 ms |
14624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
