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], timer;
  8. int up[MAXN][20], depth[MAXN];
  9. long long fenw1[MAXN*2], fenw2[MAXN*2];
  10.  
  11. void upd(long long fenw[], int i, long long v) {
  12.     for (; i <= 2*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.  
  25.     upd(fenw1, tin[u], val[u]);
  26.     upd(fenw2, tin[u], (val[u]==1));
  27.  
  28.     for (int v:g[u]) if (v!=p) {
  29.         depth[v] = depth[u]+1;
  30.         dfs(v,u);
  31.     }
  32.  
  33.     tout[u] = ++timer;
  34.     upd(fenw1, tout[u], -val[u]);
  35.     upd(fenw2, tout[u], -(val[u]==1));
  36. }
  37.  
  38. int lca(int u,int v){
  39.     if(depth[u]<depth[v]) swap(u,v);
  40.     int k=depth[u]-depth[v];
  41.     for(int i=19;i>=0;i--) if(k>>i&1) u=up[u][i];
  42.     if(u==v) return u;
  43.     for(int i=19;i>=0;i--) if(up[u][i]!=up[v][i]){
  44.         u=up[u][i]; v=up[v][i];
  45.     }
  46.     return up[u][0];
  47. }
  48.  
  49. int main() {
  50.     ios::sync_with_stdio(0);
  51.     cin.tie(0);
  52.  
  53.     cin >> n >> q;
  54.     for (int i=1;i<=n;i++) cin >> val[i];
  55.     for (int i=1;i<n;i++) {
  56.         int u,v; cin >> u >> v;
  57.         g[u].push_back(v);
  58.         g[v].push_back(u);
  59.     }
  60.  
  61.     dfs(1,1);
  62.  
  63.     while(q--) {
  64.         int u,v; cin >> u >> v;
  65.         int w = lca(u,v);
  66.  
  67.         long long sum = get(fenw1, tin[u]) + get(fenw1, tin[v]) - 2*get(fenw1, tin[w]) + val[w];
  68.         if(sum <= 0) {
  69.             cout << 0 << "\n";
  70.             continue;
  71.         }
  72.  
  73.         long long cnt = get(fenw2, tin[u]) + get(fenw2, tin[v]) - 2*get(fenw2, tin[w]) + (val[w]==1);
  74.         cout << cnt << "\n";
  75.     }
  76. }
  77.  
Success #stdin #stdout 0.01s 11280KB
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
0
3
2
https://ideone.com/PYABzx
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!