fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n,k,ans=0,timer=0,id[100005],tin[100005],tout[100005],arr[200005],bit[200005];
  4. vector <int> ve[100005];
  5. pair <int,pair<int,int>> p[100005];
  6. void DFS(int u, int p)
  7. {
  8.     tin[u]=++timer,arr[timer]=u;
  9.     for (int v : ve[u]) if (v!=p) DFS(v,u);
  10.     tout[u]=++timer,arr[timer]=u;
  11. }
  12. void UPDATE(int i, int v)
  13. {
  14.     while (i<=timer) bit[i]+=v,i+=i&(-i);
  15.     return;
  16. }
  17. int GET(int l, int r)
  18. {
  19.     l--;
  20.     int resl=0,resr=0;
  21.     while (l>0) resl+=bit[l],l-=l&(-l);
  22.     while (r>0) resr+=bit[r],r-=r&(-r);
  23.     return resr-resl;
  24. }
  25. signed main()
  26. {
  27.     ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  28.     cin>>n>>k;
  29.     for (int i=1;i<n;i++)
  30.     {
  31.         int u,v;
  32.         cin>>u>>v;
  33.         ve[u].push_back(v),ve[v].push_back(u),id[v]++;
  34.     }
  35.     int x=n;
  36.     for (int i=1;i<=n;i++) if (id[i]==0) DFS(i,0);
  37.     for (int i=n;i>=1;i--) UPDATE(tin[i],1),UPDATE(tout[i],1),ans-=GET(tin[i],tout[i])/2;
  38.     for (int i=1;i<=2*n;i++) UPDATE(i,-1);
  39.     for (int i=1;i<=n;i++) UPDATE(tin[i],1),UPDATE(tout[i],1),ans-=GET(tin[i],tout[i])/2;
  40.     for (int i=1;i<=2*n;i++) UPDATE(i,-1);
  41.     for (int i=n;i>=1;i--)
  42.     {
  43.         while (x>=1 && x>=i-k) UPDATE(tin[x],1),UPDATE(tout[x],1),x--;
  44.         ans+=GET(tin[i],tout[i])/2;
  45.     }
  46.     x=1;
  47.     for (int i=1;i<=2*n;i++) UPDATE(i,-1);
  48.     for (int i=1;i<=n;i++)
  49.     {
  50.         while (x<=n && x<=i+k) UPDATE(tin[x],1),UPDATE(tout[x],1),x++;
  51.         ans+=GET(tin[i],tout[i])/2;
  52.     }
  53.     cout<<ans;
  54.     return 0;
  55. }
Success #stdin #stdout 0.01s 7928KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/G5AAvO
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!