fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 200005;
  5. int n,q;
  6. int val[N],in[N],out[N],euler[2*N],tim=0;
  7. int dep[N],par[N][20];
  8. long long f[N];
  9. vector<int> g[N];
  10. vector<long long> comp;
  11.  
  12. void dfs(int u,int p){
  13.     in[u]=++tim; euler[tim]=u;
  14.     par[u][0]=p;
  15.     for(int i=1;i<20;i++) par[u][i]=par[par[u][i-1]][i-1];
  16.     for(int v:g[u]) if(v!=p){
  17.         dep[v]=dep[u]+1;
  18.         f[v]=f[u]+val[v];
  19.         dfs(v,u);
  20.     }
  21.     out[u]=++tim; euler[tim]=u;
  22. }
  23.  
  24. int lca(int u,int v){
  25.     if(dep[u]<dep[v]) swap(u,v);
  26.     for(int i=19;i>=0;i--) if(dep[par[u][i]]>=dep[v]) u=par[u][i];
  27.     if(u==v) return u;
  28.     for(int i=19;i>=0;i--) if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];
  29.     return par[u][0];
  30. }
  31.  
  32. struct Fenwick{
  33.     vector<int> bit;
  34.     Fenwick(int n){bit.assign(n+2,0);}
  35.     void upd(int i,int v){for(;i<(int)bit.size();i+=i&-i) bit[i]+=v;}
  36.     int get(int i){int r=0;for(;i>0;i-=i&-i) r+=bit[i];return r;}
  37.     int range(int l,int r){return get(r)-get(l-1);}
  38. };
  39.  
  40. struct Q{int l,r,u,v,lc,id;};
  41. int BLOCK;
  42. bool cmp(Q a,Q b){
  43.     if(a.l/BLOCK!=b.l/BLOCK) return a.l<b.l;
  44.     return a.r<b.r;
  45. }
  46.  
  47. int main(){
  48.     ios::sync_with_stdio(0);
  49.     cin.tie(0);
  50.     cin>>n>>q;
  51.     for(int i=1;i<=n;i++) cin>>val[i];
  52.     for(int i=1;i<n;i++){
  53.         int u,v;cin>>u>>v;
  54.         g[u].push_back(v);
  55.         g[v].push_back(u);
  56.     }
  57.     f[1]=val[1];
  58.     dfs(1,0);
  59.     comp.reserve(n);
  60.     for(int i=1;i<=n;i++) comp.push_back(f[i]);
  61.     sort(comp.begin(),comp.end());
  62.     comp.erase(unique(comp.begin(),comp.end()),comp.end());
  63.     vector<int> fid(n+1);
  64.     for(int i=1;i<=n;i++) fid[i]=lower_bound(comp.begin(),comp.end(),f[i])-comp.begin()+1;
  65.     BLOCK=sqrt(tim);
  66.     vector<Q> qs;
  67.     for(int i=1;i<=q;i++){
  68.         int u,v;cin>>u>>v;
  69.         int lc=lca(u,v);
  70.         int l=in[u],r=in[v]; if(l>r) swap(l,r);
  71.         qs.push_back({l,r,u,v,lc,i});
  72.     }
  73.     sort(qs.begin(),qs.end(),cmp);
  74.     Fenwick fw(comp.size()+5);
  75.     vector<int> on(n+1,0),ans(q+1);
  76.     auto add=[&](int idx){
  77.         int u=euler[idx]; if(!u) return;
  78.         if(on[u]){fw.upd(fid[u],-1);on[u]^=1;}
  79.         else{fw.upd(fid[u],+1);on[u]^=1;}
  80.     };
  81.     int L=1,R=0;
  82.     for(auto qu:qs){
  83.         while(L>qu.l) add(--L);
  84.         while(R<qu.r) add(++R);
  85.         while(L<qu.l) add(L++);
  86.         while(R>qu.r) add(R--);
  87.         long long need=(qu.lc==1?0:f[par[qu.lc][0]]);
  88.         int id=upper_bound(comp.begin(),comp.end(),need)-comp.begin();
  89.         ans[qu.id]=fw.range(id+1,comp.size());
  90.     }
  91.     for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
  92. }
  93.  
Success #stdin #stdout 0.01s 13768KB
comments (?)
stdin
copy 
4 4
-1
1
1
1
1 2
1 3
1 4
1 2
1 4
2 4
1 3
stdout
copy 
0
0
0
0
https://ideone.com/M63T4N
4 4
-1
1
1
1
1 2
1 3
1 4
1 2
1 4
2 4
1 3

language:
C++14 (clang 8.0)
created:
5 days 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!