fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define ll long long
  6. #define bit(n, i) ((n >> i) & 1)
  7. #define all(a) a.begin(), a.end()
  8. #define rep(i, x, n) for (int i = x; i <= n; ++i)
  9. #define red(i, x, n) for (int i = x; i >= n; --i)
  10. #define inp(a) freopen(a".inp", "r", stdin), freopen(a".out", "w", stdout)
  11.  
  12. template<class A, class B> inline void maximize(A &x, B y) {x = max(x, y);};
  13. template<class A, class B> inline void minimize(A &x, B y) {x = min(x, y);};
  14.  
  15. const int N = 1e3 + 5;
  16. const int M = 2e5 + 5;
  17. const ll MOD = 1e9 + 7;
  18.  
  19.  
  20. int n;
  21. vector<int> a[M];
  22.  
  23. int h[M], p[20][M];
  24.  
  25. void dfs(int u){
  26.     for (int v: a[u]){
  27.         if (v == p[0][u]) continue;
  28.  
  29.         p[0][v] = u; h[v] = h[u] + 1;
  30.  
  31.         rep(i, 1, 17) p[i][v] = p[i - 1][p[i - 1][v]];
  32.  
  33.         dfs(v);
  34.     }
  35. }
  36.  
  37. int LCA(int u, int v){
  38.     if (h[u] < h[v]) swap(u, v);
  39.  
  40.     int k = h[u] - h[v];
  41.  
  42.     red(i, 17, 0) if (bit(k, i))
  43.         u = p[i][u];
  44.  
  45.     if (u == v) return v;
  46.  
  47.     red(i, 17, 0) if (p[i][u] != p[i][v]){
  48.         u = p[i][u]; v = p[i][v];
  49.     }  
  50.  
  51.     return p[0][u];
  52. }
  53.  
  54. int d[M];
  55.  
  56. void DFS(int u){
  57.     for (int v: a[u]){
  58.         if (v == p[0][u]) continue;
  59.  
  60.         DFS(v);
  61.  
  62.         d[u] += d[v];
  63.     }
  64. }
  65. int main(){
  66.     cin.tie(0) -> sync_with_stdio(0);
  67.  
  68.     cin >>n;
  69.  
  70.     rep(i, 2, n){
  71.         int u, v; cin >>u >>v;
  72.  
  73.         a[u].pb(v); a[v].pb(u);
  74.     }
  75.  
  76.     dfs(1);
  77.  
  78.     int q; cin >>q;
  79.  
  80.     while (q--){
  81.         int u, v; cin >>u >>v;
  82.  
  83.         int root = LCA(u, v);
  84.  
  85.         ++d[u]; ++d[v];
  86.         --d[root];
  87.         --d[p[0][root]];
  88.     }
  89.  
  90.     DFS(1);
  91.  
  92.     int ans = 0;
  93.     rep(u, 1, n) ans += (d[u] == 0);
  94.  
  95.     cout <<ans;
  96.  
  97.     return 0;
  98. }
  99.  
Success #stdin #stdout 0.01s 24068KB
comments (?)
stdin
copy 
6
1 2
2 3
2 4
4 5
4 6
2
3 6
5 6
stdout
copy 
1
https://ideone.com/4WGZCQ
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!