fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. int n,q;
  5. vector<int>g[200005];
  6. int sz[200005];
  7. void dfs(int u,int pa) {
  8.     sz[u]=1;
  9.     for(auto v:g[u])if(v!=pa) {
  10.             dfs(v,u);
  11.             sz[u]+=sz[v];
  12.         }
  13. }
  14. vector<pair<int,int>>vec[200005];
  15. int tree[200005];
  16. void upd(int id,int val) {
  17.     while(id<=n)tree[id]+=val,id+=(id&(-id));
  18. }
  19. int get(int id) {
  20.     int sum=0;
  21.     while(id>0)sum+=tree[id],id-=(id&(-id));
  22.     return sum;
  23. }
  24. int ans[200005];
  25. void dfs_ans(int u,int pa) {
  26.     for(auto[k,id]:vec[u]) {
  27.         ans[id]=get(k);
  28.     }
  29.     for(auto v:g[u])if(v!=pa) {
  30.             upd(sz[v],-1);
  31.             upd(n-sz[v],1);
  32.             dfs_ans(v,u);
  33.             upd(sz[v],1);
  34.             upd(n-sz[v],-1);
  35.         }
  36. }
  37. int main() {
  38.     ios_base::sync_with_stdio(0);
  39.     cin.tie(0);
  40.     cout.tie(0);
  41.     cin>>n>>q;
  42.     for(int i=1; i<n; i++) {
  43.         int u,v;
  44.         cin>>u>>v;
  45.         g[u].push_back(v);
  46.         g[v].push_back(u);
  47.     }
  48.     dfs(1,0);
  49.     for(int i=1; i<=q; i++) {
  50.         int u,k;
  51.         cin>>u>>k;
  52.         vec[u].push_back({k,i});
  53.     }
  54.     for(int i=1;i<=n;i++)upd(sz[i],1);
  55.     dfs_ans(1,0);
  56.     for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
  57.     return 0;
  58. }
  59.  
Success #stdin #stdout 0.01s 14608KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HQyhg6
language:
C++ (gcc 8.3)
created:
13 hours 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!