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