fork(1) download 
  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.  
  11. void dfs(int u,int p){
  12.     in[u]=++tim; euler[tim]=u;
  13.     par[u][0]=p;
  14.     for(int i=1;i<20;i++) par[u][i]=par[par[u][i-1]][i-1];
  15.     for(int v:g[u]) if(v!=p){
  16.         dep[v]=dep[u]+1;
  17.         f[v]=f[u]+val[v];
  18.         dfs(v,u);
  19.     }
  20.     out[u]=++tim; euler[tim]=u;
  21. }
  22.  
  23. int lca(int u,int v){
  24.     if(dep[u]<dep[v]) swap(u,v);
  25.     for(int i=19;i>=0;i--) if(dep[par[u][i]]>=dep[v]) u=par[u][i];
  26.     if(u==v) return u;
  27.     for(int i=19;i>=0;i--) if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];
  28.     return par[u][0];
  29. }
  30.  
  31. struct Fenwick{
  32.     vector<int> bit;
  33.     Fenwick(int n){bit.assign(n+2,0);}
  34.     void upd(int i,int v){for(;i<(int)bit.size();i+=i&-i) bit[i]+=v;}
  35.     int get(int i){int r=0;for(;i>0;i-=i&-i) r+=bit[i];return r;}
  36.     int range(int l,int r){return get(r)-get(l-1);}
  37. };
  38.  
  39. struct Q{int l,r,u,v,lc,id;};
  40. int BLOCK;
  41. bool cmp(Q a,Q b){
  42.     if(a.l/BLOCK!=b.l/BLOCK) return a.l<b.l;
  43.     return a.r<b.r;
  44. }
  45.  
  46. int main(){
  47.     ios::sync_with_stdio(0);
  48.     cin.tie(0);
  49.  
  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.  
  60.     vector<long long> comp;
  61.     for(int i=1;i<=n;i++) comp.push_back(f[i]);
  62.     sort(comp.begin(),comp.end());
  63.     comp.erase(unique(comp.begin(),comp.end()),comp.end());
  64.     auto getId=[&](long long x){
  65.         return (int)(lower_bound(comp.begin(),comp.end(),x)-comp.begin()+1);
  66.     };
  67.     vector<int> fid(n+1);
  68.     for(int i=1;i<=n;i++) fid[i]=getId(f[i]);
  69.  
  70.     BLOCK=sqrt(tim);
  71.     vector<Q> qs;
  72.     for(int i=1;i<=q;i++){
  73.         int u,v;cin>>u>>v;
  74.         int lc=lca(u,v);
  75.         int l=in[u],r=in[v]; if(l>r) swap(l,r);
  76.         qs.push_back({l,r,u,v,lc,i});
  77.     }
  78.     sort(qs.begin(),qs.end(),cmp);
  79.  
  80.     Fenwick fw(comp.size()+5);
  81.     vector<int> on(n+1,0),ans(q+1);
  82.  
  83.     auto toggle=[&](int idx){
  84.         int u=euler[idx]; if(!u) return;
  85.         if(on[u]){ fw.upd(fid[u],-1); on[u]=0; }
  86.         else{ fw.upd(fid[u],+1); on[u]=1; }
  87.     };
  88.  
  89.     int L=1,R=0;
  90.     for(auto qu:qs){
  91.         while(L>qu.l) toggle(--L);
  92.         while(R<qu.r) toggle(++R);
  93.         while(L<qu.l) toggle(L++);
  94.         while(R>qu.r) toggle(R--);
  95.         int u=qu.u,v=qu.v,lc=qu.lc;
  96.         long long fu=f[u],flc=f[lc];
  97.         int lessU=fw.range(1,getId(fu)-1);
  98.         long long need=fu-2*flc;
  99.         int moreV=fw.range(getId(need+1),comp.size());
  100.         int res=lessU+moreV;
  101.         if(on[lc]==0){
  102.             if(f[lc]<fu) res++;
  103.             else if(f[lc]>need) res++;
  104.         }
  105.         ans[qu.id]=res;
  106.     }
  107.     for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
  108. }
  109.  
Success #stdin #stdout 0.01s 13664KB
comments (?)
stdin 
4 4
-1
1
1
1
1 2
1 3
1 4
1 2
1 4
2 4
1 3
stdout 
2
2
1
2
https://ideone.com/mrWcK8
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!