fork 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 up[MAXN][20], depth[MAXN];
  8. long long fsum[MAXN], fcnt[MAXN];
  9.  
  10. void dfs(int u, int p) {
  11.     up[u][0] = p;
  12.     for (int i=1; i<20; i++) up[u][i] = up[up[u][i-1]][i-1];
  13.     for (int v:g[u]) if (v!=p) {
  14.         depth[v] = depth[u]+1;
  15.         fsum[v] = fsum[u] + val[v];
  16.         fcnt[v] = fcnt[u] + (val[v]==1);
  17.         dfs(v,u);
  18.     }
  19. }
  20.  
  21. int lca(int u,int v) {
  22.     if(depth[u]<depth[v]) swap(u,v);
  23.     int k=depth[u]-depth[v];
  24.     for(int i=19;i>=0;i--) if(k>>i&1) u=up[u][i];
  25.     if(u==v) return u;
  26.     for(int i=19;i>=0;i--) if(up[u][i]!=up[v][i]){
  27.         u=up[u][i]; v=up[v][i];
  28.     }
  29.     return up[u][0];
  30. }
  31.  
  32. int main() {
  33.     ios::sync_with_stdio(0);
  34.     cin.tie(0);
  35.  
  36.     cin >> n >> q;
  37.     for(int i=1;i<=n;i++) cin >> val[i];
  38.     for(int i=1;i<n;i++) {
  39.         int u,v; cin >> u >> v;
  40.         g[u].push_back(v);
  41.         g[v].push_back(u);
  42.     }
  43.  
  44.     fsum[1] = val[1];
  45.     fcnt[1] = (val[1]==1);
  46.     dfs(1,1);
  47.  
  48.     while(q--) {
  49.         int u,v; cin >> u >> v;
  50.         int w = lca(u,v);
  51.         long long sum = fsum[u] + fsum[v] - 2*fsum[w] + val[w];
  52.         if(sum <= 0) {
  53.             cout << 0 << "\n";
  54.         } else {
  55.             long long cnt = fcnt[u] + fcnt[v] - 2*fcnt[w] + (val[w]==1);
  56.             cout << cnt << "\n";
  57.         }
  58.     }
  59. }
  60.  
Success #stdin #stdout 0.01s 9380KB
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/T96BTZ
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!