fork download
  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
stdin
6
1 2
2 3
2 4
4 5
4 6
2
3 6
5 6
stdout
1