Advertisement
yicongli

CF293E

Mar 5th, 2019
146
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.23 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     x=0;T k=1;char gc;
  12.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  13.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  14. }
  15.  
  16. const int N=1e5+7;
  17.  
  18. int n,L,W;
  19.  
  20. int ecnt;
  21. int fir[N],nex[N<<1],to[N<<1],w[N<<1];
  22.  
  23. inline void addedge(int u,int v,int c){
  24.     nex[++ecnt]=fir[u],fir[u]=ecnt,to[ecnt]=v,w[ecnt]=c;
  25.     nex[++ecnt]=fir[v],fir[v]=ecnt,to[ecnt]=u,w[ecnt]=c;
  26. }
  27.  
  28. int SIZE,root;
  29. int s[N];
  30. int siz[N];
  31. bool vis[N];
  32.  
  33. void getroot(int x,int f){
  34.     siz[x]=1;
  35.     s[x]=0;
  36.     for(int i=fir[x];i;i=nex[i]){
  37.         int v=to[i];
  38.         if(v==f||vis[v])continue;
  39.         getroot(v,x);
  40.         siz[x]+=siz[v];
  41.         s[x]=max(s[x],siz[v]);
  42.     }
  43.     s[x]=max(s[x],SIZE-siz[x]);
  44.     if(s[x]<s[root])root=x;
  45. }
  46.  
  47. pair<int,int>tmp[N];
  48. int tot;
  49.  
  50. void getdist(int x,int f,int dis,int dep){
  51.     //if(dis>W||dep>L)return ;
  52.     tmp[++tot]=make_pair(dis,dep);
  53.     for(int i=fir[x];i;i=nex[i]){
  54.         int v=to[i];
  55.         if(v==f||vis[v])continue;
  56.         getdist(v,x,dis+w[i],dep+1);
  57.     }
  58. }
  59.  
  60. int c[N];
  61.  
  62. inline void insert(int x){
  63.     for(int i=x+1;i<=n+1;i+=(i&-i))c[i]++;
  64. }
  65.  
  66. inline void erase(int x){
  67.     for(int i=x+1;i<=n+1;i+=(i&-i))c[i]--;
  68. }
  69.  
  70. inline ll query(int x){
  71.     if(x<0)return 0;
  72.     ll ret=0;
  73.     for(int i=x+1;i;i^=(i&-i))ret+=c[i];
  74.     return ret;
  75. }
  76.  
  77. inline ll calc(int x,int v,int d){
  78.     tot=0;
  79.     getdist(x,0,v,d);
  80.     sort(tmp+1,tmp+tot+1);
  81.     for(int i=1;i<=tot;++i){
  82.         insert(tmp[i].second);
  83.     }
  84.     int l=1,r=tot;
  85.     ll sum=0;
  86.     while(l<r){
  87.         if(tmp[l].first+tmp[r].first<=W){
  88.             erase(tmp[l].second);
  89.             sum+=query(L-tmp[l].second);
  90.             ++l;
  91.         }
  92.         else {
  93.             erase(tmp[r].second);
  94.             --r;
  95.         }
  96.     }
  97.     erase(tmp[l].second);
  98.     return sum;
  99. }
  100.  
  101. ll ans;
  102.  
  103. void solve(int x,int size){
  104.     ans+=calc(x,0,0);
  105.     vis[x]=1;
  106.     for(int i=fir[x];i;i=nex[i]){
  107.         int v=to[i];
  108.         if(vis[v])continue;
  109.         ans-=calc(v,w[i],1);
  110.         s[root=0]=SIZE=(siz[v]>siz[x]?size-siz[x]:siz[v]);
  111.         getroot(v,0);
  112.         solve(root,SIZE);
  113.     }
  114. }
  115.  
  116. int main(){
  117. //  freopen(".in","r",stdin);
  118. //  freopen(".out","w",stdout);
  119.     r(n),r(L),r(W);
  120.     for(int i=2;i<=n;++i){
  121.         int v,w;r(v),r(w);
  122.         addedge(i,v,w);
  123.     }
  124.     s[root]=SIZE=n;
  125.     getroot(1,0);
  126.     solve(root,n);
  127.     cout<<ans;
  128.     return 0;
  129. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement