fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define FILE "SHIP"
  4.  
  5. #define int long long
  6. #define ii pair<int, int>
  7.  
  8. #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  9. #define FOR(I, L, R) for(int I = (int)L; I <= (int)R; I++)
  10. #define FOD(I, R, L) for(int I = (int)R; I >= (int)L; I--)
  11. #define FOA(I, A) for(auto &I : A)
  12.  
  13. #define all(A) A.begin(), A.end()
  14. #define fi first
  15. #define se second
  16.  
  17. const int N = 2e5 + 10;
  18. const int oo = 1e18;
  19. const int mod = 1e9 + 7;
  20.  
  21. int n, q;
  22. vector<int> g[N];
  23. int lazy[N];
  24. int c;
  25. int h[N], up[N][20];
  26.  
  27.  
  28. void dfs(int u, int p){
  29.      FOA(v, g[u]) if(v != p){
  30.           h[v] = h[u] + 1;
  31.           up[v][0] = u;
  32.  
  33.           FOR(i, 1, 18){
  34.                up[v][i] = up[up[v][i - 1]][i - 1];
  35.           }
  36.  
  37.           dfs(v, u);
  38.      }
  39. }
  40.  
  41. int lca(int u, int v){
  42.      if(h[u] > h[v]) swap(u, v);
  43.  
  44.      int c = h[v] - h[u];
  45.  
  46.      FOR(i, 0, 18){
  47.           if(c >> i & 1){
  48.                v = up[v][i];
  49.           }
  50.      }
  51.  
  52.      if(v == u) return u;
  53.  
  54.      FOR(i, 0, 18){
  55.           if(up[u][i] == up[v][i]) continue;
  56.  
  57.           u = up[u][i];
  58.           v = up[v][i];
  59.      }
  60.  
  61.      return up[u][0];
  62. }
  63.  
  64. int ans;
  65. void dp(int u, int p){
  66.      FOA(v, g[u]) if(v != p){
  67.           dp(v, u);
  68.           if(lazy[v] == 0) ans++;
  69.           lazy[u] += lazy[v];
  70.      }
  71. }
  72.  
  73. signed main(){ fast
  74.      if(fopen(FILE ".INP", "r")){
  75.           freopen(FILE".INP", "r", stdin);
  76.           freopen(FILE".OUT", "w", stdout);
  77.      }
  78.  
  79.      cin >> n;
  80.      FOR(i, 1, n - 1){
  81.           int u, v;
  82.           cin >> u >> v;
  83.           g[u].push_back(v);
  84.           g[v].push_back(u);
  85.      }
  86.      dfs(1, 0);
  87.  
  88.      cin >> q;
  89.      while(q--){
  90.           int u, v;
  91.           cin >> u >> v;
  92.  
  93.           lazy[u]++;
  94.           lazy[v]++;
  95.           lazy[lca(u, v)] -= 2;
  96.      }
  97.      dp(1, 0);
  98.  
  99.      cout << ans;
  100. }
  101.  
Success #stdin #stdout 0.01s 9260KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kLBNm8
language:
C++ (gcc 8.3)
created:
1 day 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!