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. bool d[M];
  24.  
  25. void BFS(int A, int B){
  26. queue<int> q;
  27. vector<int> trace(n + 1, 0);
  28.  
  29. d[A] = 1; q.push(A);
  30. trace[A] = -1;
  31.  
  32. while (q.size()){
  33. int u = q.front(); q.pop();
  34.  
  35. for (int v: a[u]) if (trace[v] == 0){
  36. trace[v] = u;
  37.  
  38. if (v == B) break;
  39.  
  40. q.push(v);
  41. }
  42. }
  43.  
  44. while (B != A){
  45. d[B] = 1; B = trace[B];
  46. }
  47. }
  48. int main(){
  49. cin.tie(0) -> sync_with_stdio(0);
  50.  
  51. cin >>n;
  52.  
  53. rep(i, 2, n){
  54. int u, v; cin >>u >>v;
  55.  
  56. a[u].pb(v); a[v].pb(u);
  57. }
  58.  
  59. int q; cin >>q;
  60.  
  61. while (q--){
  62. int A, B; cin >>A >>B;
  63.  
  64. BFS(A, B);
  65. }
  66.  
  67. int cnt = 0;
  68. rep(u, 1, n) if (d[u] == 0) ++cnt;
  69.  
  70. cout <<cnt;
  71.  
  72. return 0;
  73. }
  74.  
Success #stdin #stdout 0.01s 8288KB
stdin
6
1 2
2 3
2 4
4 5
4 6
2
3 6
5 6
stdout
1