Advertisement
MinhNGUYEN2k4

Untitled

Feb 19th, 2022
973
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.21 KB | None | 0 0
  1. //Nguyen Huu Hoang Minh
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define all(x) x.begin(),x.end()
  5. #define reset(x) memset(x, 0,sizeof(x))
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define N 200005
  11. #define remain(x) if (x > MOD) x -= MOD
  12. #define ii pair<int, int>
  13. #define iiii pair< ii , ii >
  14. #define viiii vector< iiii >
  15. #define vi vector<int>
  16. #define vii vector< ii >
  17. #define bit(x, i) (((x) >> (i)) & 1)
  18. #define Task "test"
  19.  
  20. using namespace std;
  21.  
  22. typedef long double ld;
  23.  
  24. int n, m;
  25. vector<int> g[N];
  26.  
  27. void readfile()
  28. {
  29.     ios_base::sync_with_stdio(false);
  30.     cin.tie(0);cout.tie(0);
  31.     if (fopen(Task".inp","r"))
  32.     {
  33.         freopen(Task".inp","r",stdin);
  34.         //freopen(Task".out","w",stdout);
  35.     }
  36.     cin >> n;
  37.     for(int i=1; i<n; i++){
  38.         int u, v; cin >> u >> v;
  39.         g[u].pb(v);
  40.         g[v].pb(u);
  41.     }
  42. }
  43.  
  44. int Start[N], Depth[N], Time, Par[N];
  45. ii RMQ[21][N*2];
  46.  
  47. void DFS(int u, int p=-1){
  48.     Start[u] = ++Time;
  49.     RMQ[0][Time] = ii(Depth[u], u);
  50.     for (int v : g[u]){
  51.         if (v != p){
  52.             Depth[v] = Depth[u] + 1;
  53.             Par[v] = u;
  54.             DFS(v, u);
  55.             RMQ[0][++Time] = ii(Depth[u], u);
  56.         }
  57.     }
  58. }
  59.  
  60. void Preprocess(){
  61.     DFS(1);
  62.     int LIM = log2(Time);
  63.     for (int i = 1; i <= LIM; ++i){
  64.         for (int j = 1; j + (1 << i) - 1 <= Time; ++j){
  65.             RMQ[i][j] = min(RMQ[i-1][j], RMQ[i-1][j + (1 << (i-1))]);
  66.         }
  67.     }
  68. }
  69.  
  70. int LCA(int u, int v){
  71.     int Left = min(Start[u], Start[v]);
  72.     int Right = max(Start[u], Start[v]);
  73.     int len = log2(Right - Left + 1);
  74.     return min(RMQ[len][Left], RMQ[len][Right - (1 << len) + 1]).se;
  75. }
  76.  
  77. int ans = 0, vst[N];
  78.  
  79. void fix(int u, int par){
  80.     for(auto v : g[u]){
  81.         if (v==par) continue;
  82.         fix(v,u);
  83.         vst[u] += vst[v];
  84.     }
  85.     if (vst[u]==0) ans++;
  86. }
  87.  
  88. void proc()
  89. {
  90.     Preprocess();
  91.     cin >> m;
  92.     for(int i=1; i<=m; i++){
  93.         int u, v, z;
  94.         cin >> u >> v;
  95.         z = LCA(u,v);
  96.         vst[u]++; vst[v]++;
  97.         vst[z]--; vst[Par[z]]--;
  98.     }
  99.     fix(1,1);
  100.     cout << ans;
  101. }
  102.  
  103. signed main()
  104. {
  105.     readfile();
  106.     proc();
  107.     return 0;
  108. }
  109.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement