Guest User

Untitled

a guest
Jan 29th, 2017
69
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. typedef  long long ll;
  3. using namespace std;
  4. ll arr[200005];
  5. ll depth[200005];
  6. int fin[200005];
  7. ll wt[200005];
  8. std::vector< pair<ll,int> >::iterator high;
  9.  
  10. bool cmp(int val, pair<ll,int> p1){
  11.   return val<p1.first;
  12. }
  13. void dfs1(vector<vector<int > > g, int v, int d, std::vector<pair<ll,int> > ls){
  14.   depth[v]=d;
  15.   if(g[v].size()==0){
  16.     high=upper_bound(ls.begin(),ls.end(),depth[v]-arr[v]-1,cmp);
  17.     int i=high-ls.begin();
  18.     for(;i<ls.size();i++)
  19.       fin[ls[i].second]++;
  20.     return ;
  21.   }
  22.   ls.push_back(make_pair(d,v));
  23.   for(int i=0;i<g[v].size();i++){
  24.     dfs1(g,g[v][i],d+wt[g[v][i]],ls);
  25.   }
  26.   ls.pop_back();
  27.   high=upper_bound(ls.begin(),ls.end(),depth[v]-arr[v]-1,cmp);
  28.   int i=high-ls.begin();
  29.   for(;i<ls.size();i++)
  30.     fin[ls[i].second]++;
  31.   return ;
  32. }
  33.  
  34. int main(){
  35.   ios::sync_with_stdio(false);
  36.   memset(fin,0,sizeof(fin));
  37.   int n;
  38.   cin>>n;
  39.   for(int i=0;i<n;i++)
  40.     cin>>arr[i];
  41.   std::vector< std::vector<int> > g(n);
  42.   for(int i=1;i<n;i++){
  43.     int p;
  44.     ll w;
  45.     cin>>p>>w;
  46.     p--;
  47.     g[p].push_back(i);
  48.     wt[i]=w;
  49.   }
  50.   std::vector<pair<ll,int> > ls;
  51.   dfs1(g,0,0,ls);
  52.   for(int i=0;i<n;i++)
  53.     cout<<fin[i]<<" ";
  54. }
RAW Paste Data