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