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], tout[MAXN], euler[2*MAXN], timer;
  8. int up[MAXN][20], depth[MAXN];
  9. long long fenw[MAXN*2];
  10.  
  11. void upd(int i, long long v) {
  12.     for (; i <= 2*n; i += i&-i) fenw[i] += v;
  13. }
  14. long long get(int i) {
  15.     long long r = 0;
  16.     for (; i; i -= i&-i) r += fenw[i];
  17.     return r;
  18. }
  19. long long query(int l, int r) {
  20.     return get(r) - get(l-1);
  21. }
  22.  
  23. void dfs(int u, int p) {
  24.     tin[u] = ++timer;
  25.     euler[timer] = u;
  26.     up[u][0] = p;
  27.     for (int i=1; i<20; i++) up[u][i] = up[up[u][i-1]][i-1];
  28.     for (int v:g[u]) if (v!=p) {
  29.         depth[v] = depth[u]+1;
  30.         dfs(v,u);
  31.     }
  32.     tout[u] = ++timer;
  33.     euler[timer] = -u;
  34. }
  35.  
  36. int lca(int u,int v){
  37.     if(depth[u]<depth[v]) swap(u,v);
  38.     int k=depth[u]-depth[v];
  39.     for(int i=19;i>=0;i--) if(k>>i&1) u=up[u][i];
  40.     if(u==v) return u;
  41.     for(int i=19;i>=0;i--) if(up[u][i]!=up[v][i]){
  42.         u=up[u][i]; v=up[v][i];
  43.     }
  44.     return up[u][0];
  45. }
  46.  
  47. int main(){
  48.     ios::sync_with_stdio(0);
  49.     cin.tie(0);
  50.     cin>>n>>q;
  51.     for(int i=1;i<=n;i++) cin>>val[i];
  52.     for(int i=1;i<n;i++){
  53.         int u,v; cin>>u>>v;
  54.         g[u].push_back(v);
  55.         g[v].push_back(u);
  56.     }
  57.     dfs(1,1);
  58.     for(int i=1;i<=2*n;i++){
  59.         int u=euler[i];
  60.         if(u>0) upd(i,val[u]);
  61.         else upd(i,-val[-u]);
  62.     }
  63.     while(q--){
  64.         int u,v; cin>>u>>v;
  65.         int w=lca(u,v);
  66.         long long sum=query(tin[u],tin[v])+val[w];
  67.         int ans=0;
  68.         if(sum>0){
  69.             if(depth[u]<depth[v]) swap(u,v);
  70.             while(u!=w){
  71.                 if(val[u]==1) ans++;
  72.                 u=up[u][0];
  73.             }
  74.             while(v!=w){
  75.                 if(val[v]==1) ans++;
  76.                 v=up[v][0];
  77.             }
  78.             if(val[w]==1) ans++;
  79.         }
  80.         cout<<ans<<"\n";
  81.     }
  82. }
  83.  
Success #stdin #stdout 0.01s 7148KB
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/Rcef1o
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!