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