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