fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const int LOG = 20;
  5.  
  6. struct BIT {
  7.     int n; vector<int> b;
  8.     void init(int _n){ n=_n; b.assign(n+1,0); }
  9.     void add(int i,int v){ for(; i<=n; i+=i&-i) b[i]+=v; }
  10.     int sum(int i){ int r=0; for(; i>0; i-=i&-i) r+=b[i]; return r; }
  11. };
  12.  
  13. int main(){
  14.     ios::sync_with_stdio(false);
  15.     cin.tie(nullptr);
  16.     int n,q;
  17.     if(!(cin>>n>>q)) return 0;
  18.     vector<int> val(n+1);
  19.     for(int i=1;i<=n;i++) cin>>val[i];
  20.     vector<vector<int>> g(n+1);
  21.     for(int i=1;i<n;i++){
  22.         int u,v; cin>>u>>v;
  23.         g[u].push_back(v); g[v].push_back(u);
  24.     }
  25.  
  26.     vector<array<int,LOG>> up(n+1);
  27.     vector<int> depth(n+1,0);
  28.     vector<ll> f(n+1,0);
  29.  
  30.     function<void(int,int)> dfs0 = [&](int u,int p){
  31.         up[u][0]=p;
  32.         for(int j=1;j<LOG;j++) up[u][j]=up[ up[u][j-1] ][j-1];
  33.         for(int v: g[u]) if(v!=p){
  34.             depth[v]=depth[u]+1;
  35.             f[v]=f[u]+val[v];
  36.             dfs0(v,u);
  37.         }
  38.     };
  39.     f[1]=val[1];
  40.     dfs0(1,0);
  41.  
  42.     auto lca = [&](int a,int b){
  43.         if(depth[a]<depth[b]) swap(a,b);
  44.         int k = depth[a]-depth[b];
  45.         for(int j=LOG-1;j>=0;j--) if(k>>j & 1) a = up[a][j];
  46.         if(a==b) return a;
  47.         for(int j=LOG-1;j>=0;j--) if(up[a][j]!=up[b][j]){ a=up[a][j]; b=up[b][j]; }
  48.         return up[a][0];
  49.     };
  50.  
  51.     vector<int> U(q+1), V(q+1), W(q+1);
  52.     vector<ll> T(q+1);
  53.     vector<ll> vals;
  54.     vals.reserve(n+q+5);
  55.     for(int i=1;i<=n;i++) vals.push_back(f[i]);
  56.  
  57.     for(int i=1;i<=q;i++){
  58.         int u,v; cin>>u>>v;
  59.         U[i]=u; V[i]=v;
  60.         W[i]=lca(u,v);
  61.         T[i]=f[u]-val[u];
  62.         vals.push_back(T[i]);
  63.     }
  64.  
  65.     sort(vals.begin(), vals.end());
  66.     vals.erase(unique(vals.begin(), vals.end()), vals.end());
  67.     int M = (int)vals.size();
  68.  
  69.     auto posF = [&](ll x){ return (int)(lower_bound(vals.begin(), vals.end(), x) - vals.begin()) + 1; };
  70.     auto posLE  = [&](ll x){ return (int)(upper_bound(vals.begin(), vals.end(), x) - vals.begin()); };
  71.  
  72.     vector<int> fpos(n+1);
  73.     for(int i=1;i<=n;i++) fpos[i]=posF(f[i]);
  74.  
  75.     vector<int> needpos(q+1);
  76.     for(int i=1;i<=q;i++) needpos[i]=posLE(T[i]);
  77.  
  78.     vector<vector<tuple<int,int,int>>> gu(n+1);
  79.     for(int i=1;i<=q;i++){
  80.         gu[U[i]].push_back({i, needpos[i], +1});
  81.         gu[V[i]].push_back({i, needpos[i], +1});
  82.         gu[W[i]].push_back({i, needpos[i], -2});
  83.     }
  84.  
  85.     vector<ll> ans(q+1,0);
  86.     for(int i=1;i<=q;i++) if(f[ W[i] ] > T[i]) ans[i]++;
  87.  
  88.     BIT bit; bit.init(max(1,M));
  89.     function<void(int,int)> dfs = [&](int u,int p){
  90.         bit.add(fpos[u],1);
  91.         for(auto &t: gu[u]){
  92.             int id, idx, sign; tie(id, idx, sign) = t;
  93.             int greater = bit.sum(M) - bit.sum(idx);
  94.             ans[id] += 1LL * sign * greater;
  95.         }
  96.         for(int v: g[u]) if(v!=p) dfs(v,u);
  97.         bit.add(fpos[u],-1);
  98.     };
  99.     dfs(1,0);
  100.  
  101.     for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
  102.     return 0;
  103. }
  104.  
Success #stdin #stdout 0s 5324KB
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 
1
1
0
2
2
https://ideone.com/wpOqHH
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!