fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 100005;
  5. int n, q, val[MAXN];
  6. vector<int> g[MAXN];
  7. int tin[MAXN], timer;
  8. int up[MAXN][20], depth[MAXN];
  9. long long fenw1[MAXN], fenw2[MAXN];
  10.  
  11. void upd(long long fenw[], int i, long long v) {
  12.     for (; i<=n; i+=i&-i) fenw[i]+=v;
  13. }
  14. long long get(long long fenw[], int i) {
  15.     long long r=0;
  16.     for(;i;i-=i&-i) r+=fenw[i];
  17.     return r;
  18. }
  19.  
  20. void dfs(int u,int p){
  21.     tin[u]=++timer;
  22.     up[u][0]=p;
  23.     for(int i=1;i<20;i++) up[u][i]=up[up[u][i-1]][i-1];
  24.     for(int v:g[u]) if(v!=p){
  25.         depth[v]=depth[u]+1;
  26.         dfs(v,u);
  27.     }
  28. }
  29.  
  30. int lca(int u,int v){
  31.     if(depth[u]<depth[v]) swap(u,v);
  32.     int k=depth[u]-depth[v];
  33.     for(int i=19;i>=0;i--) if(k>>i&1) u=up[u][i];
  34.     if(u==v) return u;
  35.     for(int i=19;i>=0;i--) if(up[u][i]!=up[v][i]){
  36.         u=up[u][i]; v=up[v][i];
  37.     }
  38.     return up[u][0];
  39. }
  40.  
  41. int main(){
  42.     ios::sync_with_stdio(0);
  43.     cin.tie(0);
  44.     cin>>n>>q;
  45.     for(int i=1;i<=n;i++) cin>>val[i];
  46.     for(int i=1;i<n;i++){
  47.         int u,v;cin>>u>>v;
  48.         g[u].push_back(v);
  49.         g[v].push_back(u);
  50.     }
  51.     dfs(1,1);
  52.     for(int i=1;i<=n;i++){
  53.         upd(fenw1,tin[i],val[i]);
  54.         upd(fenw2,tin[i],(val[i]==1));
  55.     }
  56.     while(q--){
  57.         int u,v;cin>>u>>v;
  58.         int w=lca(u,v);
  59.         long long sum=get(fenw1,tin[u])+get(fenw1,tin[v])-2*get(fenw1,tin[w])+val[w];
  60.         if(sum<=0){
  61.             cout<<0<<"\n";
  62.         }else{
  63.             long long cnt=get(fenw2,tin[u])+get(fenw2,tin[v])-2*get(fenw2,tin[w])+(val[w]==1);
  64.             cout<<cnt<<"\n";
  65.         }
  66.     }
  67. }
  68.  
Success #stdin #stdout 0.01s 7292KB
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 
6
1
4
9
4
https://ideone.com/rsoNke
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!