This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//copied cause im not spending any more time doing stupid constant optimization
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std ;
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update> ;
const int MAX = 1e5 + 10 ;
int arr[MAX] , sz[MAX] , mark[MAX] ;
int n ;
vector< vector< pair<int , int> > >adj(MAX) ;
//centroid decomposition
void dfs(int node , int par)
{
sz[node] = 1 ;
for(auto &child : adj[node])
{
if(child.first == par || mark[child.first])
continue ;
dfs(child.first , node) ;
sz[node] += sz[child.first] ;
}
}
int Findcentroid(int node , int par , int sub_sz)
{
for(auto &child : adj[node])
{
if(mark[child.first] || child.first == par)
continue ;
if(sz[child.first] > sub_sz / 2)
return Findcentroid(child.first , node , sub_sz) ;
}
return node ;
}
ordered_set< pair<long long , int> >s[MAX] ;
long long ans = 0ll ;
int centroid ;
bool flag ;
void Insert(int node , int par , long long x , long long Min)
{
Min = min(Min , x) ;
if(Min >= 0)
ans += flag ;
s[centroid].insert({Min * -1ll , node}) ;
for(auto &child : adj[node])
{
if(child.first == par || mark[child.first])
continue ;
Insert(child.first , node , x + arr[node] - child.second , Min) ;
}
}
void Query(int node , int par , long long sum , long long Min)
{
if(Min >= 0)
ans += s[centroid].order_of_key({sum+1 , -1}) , ans += flag ;
for(auto &child : adj[node])
{
if(child.first == par || mark[child.first])
continue ;
long long x = arr[child.first] - child.second ;
Query(child.first , node , sum + x , min(Min + x , x)) ;
}
}
void solve()
{
flag = true ;
for(auto &child : adj[centroid])
{
if(mark[child.first])
continue ;
Query(child.first , -1 , arr[child.first] - child.second , arr[child.first] - child.second) ;
Insert(child.first , -1 , arr[centroid] - child.second , 0) ;
}
s[centroid].clear() ;
reverse(adj[centroid].begin() , adj[centroid].end()) ;
flag = false ;
for(auto &child : adj[centroid])
{
if(mark[child.first])
continue ;
Query(child.first , -1 , arr[child.first] - child.second , arr[child.first] - child.second) ;
Insert(child.first , -1 , arr[centroid] - child.second , 0) ;
}
s[centroid].clear() ;
}
void build(int node)
{
dfs(node , -1) ;
centroid = Findcentroid(node , -1 , sz[node]) ;
mark[centroid] = 1 ;
solve() ;
for(auto &child : adj[centroid])
{
if(!mark[child.first])
build(child.first) ;
}
}
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>n ;
for(int i = 1 ; i <= n ; ++i)
cin>>arr[i] ;
for(int i = 0 ; i < n-1 ; ++i)
{
int x , y , z ;
cin>>x>>y>>z ;
adj[x].push_back({y , z}) ;
adj[y].push_back({x , z}) ;
}
build(1) ;
return cout<<ans<<"\n" , 0 ;
}
# | 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... |