fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Fenwick {
  5.     int n; vector<int> bit;
  6.     Fenwick(int n=0): n(n), bit(n+1,0) {}
  7.     void add(int i,int v){ for(; i<=n; i+=i&-i) bit[i]+=v; }
  8.     int sumPrefix(int i){ int s=0; for(; i>0; i-=i&-i) s+=bit[i]; return s; }
  9.     int sumRange(int l,int r){ if(r<l) return 0; return sumPrefix(r)-sumPrefix(l-1); }
  10. };
  11.  
  12. int main(){
  13.     ios::sync_with_stdio(false);
  14.     cin.tie(nullptr);
  15.     int n,q; 
  16.     if(!(cin>>n>>q)) return 0;
  17.     vector<int> a(n+1);
  18.     for(int i=1;i<=n;i++) cin>>a[i];
  19.     vector<vector<int>> g(n+1);
  20.     for(int i=0,u,v;i<n-1;i++){ cin>>u>>v; g[u].push_back(v); g[v].push_back(u); }
  21.     int LOG=20;
  22.     vector<int> depth(n+1), parent(n+1);
  23.     vector<vector<int>> up(LOG, vector<int>(n+1));
  24.     vector<long long> f(n+1);
  25.     function<void(int,int)> dfs1 = [&](int u,int p){
  26.         parent[u]=p; up[0][u]=p; depth[u]=(p?depth[p]+1:0);
  27.         f[u]= (p?f[p]:0) + a[u];
  28.         for(int k=1;k<LOG;k++) up[k][u]= up[k-1][u]? up[k-1][ up[k-1][u] ]:0;
  29.         for(int v: g[u]) if(v!=p) dfs1(v,u);
  30.     };
  31.     dfs1(1,0);
  32.     auto lca = [&](int u,int v){
  33.         if(depth[u]<depth[v]) swap(u,v);
  34.         int d=depth[u]-depth[v];
  35.         for(int k=0;k<LOG;k++) if(d>>k&1) u=up[k][u];
  36.         if(u==v) return u;
  37.         for(int k=LOG-1;k>=0;k--) if(up[k][u]!=up[k][v]){ u=up[k][u]; v=up[k][v]; }
  38.         return up[0][u];
  39.     };
  40.     struct Item{ long long need; int id,which; };
  41.     vector<vector<Item>> at(n+1);
  42.     vector<long long> need(q), chk(q);
  43.     vector<int> cu(q), cv(q), cl(q);
  44.     vector<long long> coord;
  45.     for(int i=1;i<=n;i++) coord.push_back(f[i]);
  46.     vector<pair<int,int>> qs(q);
  47.     for(int i=0;i<q;i++){
  48.         int u,v; cin>>u>>v; qs[i]={u,v};
  49.         int L=lca(u,v);
  50.         long long nd = f[u] - 2LL*f[L];
  51.         need[i]=nd;
  52.         chk[i] = (f[L] > nd);
  53.         at[u].push_back({nd,i,0});
  54.         at[v].push_back({nd,i,1});
  55.         at[L].push_back({nd,i,2});
  56.         coord.push_back(nd);
  57.     }
  58.     sort(coord.begin(), coord.end());
  59.     coord.erase(unique(coord.begin(), coord.end()), coord.end());
  60.     auto idx = [&](long long x){ return int(upper_bound(coord.begin(), coord.end(), x) - coord.begin()); };
  61.     Fenwick bit((int)coord.size()+2);
  62.     function<void(int,int)> dfs2 = [&](int u,int p){
  63.         bit.add(idx(f[u])+1,1);
  64.         for(auto &it: at[u]){
  65.             int pos = idx(it.need)+1;
  66.             int greater = bit.sumRange(pos+1, bit.n);
  67.             if(it.which==0) cu[it.id]=greater;
  68.             else if(it.which==1) cv[it.id]=greater;
  69.             else cl[it.id]=greater;
  70.         }
  71.         for(int v: g[u]) if(v!=p) dfs2(v,u);
  72.         bit.add(idx(f[u])+1,-1);
  73.     };
  74.     dfs2(1,0);
  75.     for(int i=0;i<q;i++){
  76.         long long ans = (long long)cu[i] + cv[i] - 2LL*cl[i] + chk[i];
  77.         cout<<ans<<"\n";
  78.     }
  79.     return 0;
  80. }
  81.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
8 5
-1 1 1 1 -1 1 1  -1
1 5
5 6
3 6
4 5
4 7
4 8
1 2
3 8
2 2
1 7
2 7
6 4
stdout
copy 
0
0
0
0
0
https://ideone.com/muBRIc
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!