Advertisement
Josif_tepe

Untitled

Nov 16th, 2023
899
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.15 KB | None | 0 0
  1. #include <iostream>
  2. //#include <bits/stdc++.h>
  3. using namespace std;
  4. const int maxn = 2e5 + 2;
  5. const int logn = 19;
  6. int n, q;
  7. vector<int> graph[maxn];
  8. int in_dfs[maxn], out_dfs[maxn];
  9. int pref_sum[maxn];
  10. int up_node[maxn][logn];
  11. int timer = 0;
  12. void dfs(int node, int parent) {
  13.     timer++;
  14.     in_dfs[node] = timer;
  15.     up_node[node][0] = parent;
  16.     for(int i = 1; i < logn; i++) {
  17.         up_node[node][i] = up_node[up_node[node][i - 1]][i - 1];
  18.     }
  19.     for(int neighbour : graph[node]) {
  20.         if(neighbour != parent) {
  21.             dfs(neighbour, node);
  22.         }
  23.     }
  24.     timer++;
  25.     out_dfs[node] = timer;
  26.    
  27. }
  28. bool is_ancestor(int A, int B) {
  29.     if(in_dfs[A] <= in_dfs[B] and out_dfs[A] >= out_dfs[B]) {
  30.         return true;
  31.     }
  32.     return false;
  33. }
  34. int LCA(int A, int B) {
  35.     if(is_ancestor(A, B)) {
  36.         return A;
  37.     }
  38.     if(is_ancestor(B, A)) {
  39.         return B;
  40.     }
  41.     for(int i = logn - 1; i >= 0; i--) {
  42.         if(!is_ancestor(up_node[A][i], B)) {
  43.             A = up_node[A][i];
  44.         }
  45.     }
  46. //    cout << A << endl;
  47.     if(A == 0) {
  48.         return 1;
  49.     }
  50.     return up_node[A][0];
  51. }
  52. void pref_dfs(int node) {
  53.     for(int neighbour : graph[node]) {
  54.         if(neighbour != up_node[neighbour][0]) {
  55.             pref_dfs(neighbour);
  56.             pref_sum[node] += pref_sum[neighbour];
  57.         }
  58.     }
  59. }
  60. int main(){
  61.     ios_base::sync_with_stdio(false);
  62.     cin >> n >> q;
  63.    
  64.     for(int i = 1; i < n; i++) {
  65.         int a, b;
  66.         cin >> a >> b;
  67.         graph[a].push_back(b);
  68.         graph[b].push_back(a);
  69.     }
  70.     dfs(1, -1);
  71.     for(int i = 0; i < q; i++) {
  72.         int a, b;
  73.         cin >> a >> b;
  74.        
  75.         pref_sum[a]++;
  76.         pref_sum[b]++;
  77.         int lca = LCA(a, b);
  78. //        cout << a << " "<< b << " " << lca<< endl;
  79.         pref_sum[lca]--;
  80.         if(lca != 1) {
  81.             pref_sum[up_node[lca][0]]--;
  82.         }
  83.     }
  84. //    for(int i = 1; i <= n; i++) {
  85. //        cout << pref_sum[i] << " ";
  86. //    }
  87. //    cout << endl;
  88.     pref_dfs(1);
  89.    
  90.     for(int i = 1; i <= n; i++) {
  91.         cout << pref_sum[i] << " ";
  92.     }
  93.     return 0;
  94. }
  95.  
  96.  
  97.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement