#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#define pb push_back
#define mp make_pair
#define taskname "A"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <pair<ll,int>,null_type,less<pair<ll,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const int logn = log2(maxn) + 1;
bool vis[maxn];
vector<ii> adj[maxn];
int sub[maxn] , big[maxn];
void dfs(int u , int par){
sub[u] = 1;
big[u] = -1;
for(auto & c : adj[u]){
if(vis[c.first] || c.first == par)continue;
dfs(c.first , u);
sub[u] += sub[c.first];
if(big[u] == -1 || sub[big[u]] < sub[c.first])big[u] = c.first;
}
}
ll res = 0;
int n , a[maxn];
ll b[maxn] , c[maxn];
vector<int> val;
int P[maxn];
void dfs1(int u , int par , ll cur , ll need , ll cur1){
val.pb(u);
need = min(need , cur);
cur += a[u];
if(par != 0 && P[par] == 0)P[u] = u;
else P[u] = P[par];
// cout << u << " " << P[u] << endl;
if(cur1 < 0)c[u] = -1;
else c[u] = cur;
b[u] = need;
for(auto c : adj[u]){
if(c.first == par || vis[c.first] == 1)continue;
dfs1(c.first , u , cur - c.second , need , min(0ll , cur1) + a[c.first] - c.second);
}
}
void solve(int u){
dfs(u , 0);
int tot = sub[u];
while(big[u] != -1 && sub[big[u]] * 2 >= tot)u = big[u];
val.clear();
dfs1(u , 0 , 0 , 0 , 0);
vis[u] = 1;
ordered_set s;
int j = 0;
for(auto &c : val){
while(j < val.size() && P[c] != P[val[j]])s.insert(mp(-b[val[j]] , val[j])) , ++j;
if(::c[c] - a[u] >= 0)res += s.order_of_key(mp(::c[c] - a[u] + 1 , 0));
}
s.clear();
j = 0;
reverse(val.begin(),val.end());
for(auto &c : val){
while(j < val.size() && P[c] != P[val[j]])s.insert(mp(-b[val[j]] , val[j])) , ++j;
if(::c[c] - a[u] >= 0)res += s.order_of_key(mp(::c[c] - a[u] + 1 , 0));
}
// cout << "S " << u << endl;
// cout << res << endl;
// for(auto & c : val)cout << c << " " << b[c] << " " << ::c[c] - a[u] << " " << P[c] << endl;
// for(int i = 1 ; i <= n ; ++i)cout << b[i] << " " << c[i] << endl;
s.clear();
for(auto c : adj[u]){
if(vis[c.first] == 0)solve(c.first);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen(taskname".INP","r")){
freopen(taskname".INP", "r",stdin);
freopen(taskname".OUT", "w",stdout);
}
cin >> n;
for(int i = 1 ; i <= n ; ++i)cin >> a[i];
for(int i = 1 ; i < n ; ++i){
int u , v , c;cin >> u >> v >> c;
adj[u].pb(mp(v , c));
adj[v].pb(mp(u , c));
}
solve(1);
cout << res;
}
Compilation message
transport.cpp: In function 'void solve(int)':
transport.cpp:67:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j < val.size() && P[c] != P[val[j]])s.insert(mp(-b[val[j]] , val[j])) , ++j;
~~^~~~~~~~~~~~
transport.cpp:74:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j < val.size() && P[c] != P[val[j]])s.insert(mp(-b[val[j]] , val[j])) , ++j;
~~^~~~~~~~~~~~
transport.cpp: In function 'int main()':
transport.cpp:92:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(taskname".INP", "r",stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
transport.cpp:93:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(taskname".OUT", "w",stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
3200 KB |
Output is correct |
| 2 |
Correct |
16 ms |
3432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
3456 KB |
Output is correct |
| 2 |
Correct |
24 ms |
3712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
225 ms |
10744 KB |
Output is correct |
| 2 |
Correct |
193 ms |
10616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
310 ms |
13568 KB |
Output is correct |
| 2 |
Correct |
335 ms |
16348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
451 ms |
17396 KB |
Output is correct |
| 2 |
Correct |
540 ms |
23024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
161 ms |
6648 KB |
Output is correct |
| 2 |
Correct |
90 ms |
6648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
177 ms |
9332 KB |
Output is correct |
| 2 |
Correct |
254 ms |
9464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
343 ms |
11252 KB |
Output is correct |
| 2 |
Correct |
327 ms |
13044 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
457 ms |
13552 KB |
Output is correct |
| 2 |
Correct |
458 ms |
15732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
626 ms |
16792 KB |
Output is correct |
| 2 |
Correct |
563 ms |
17524 KB |
Output is correct |
