fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. const int MAXN   = 100000;
  6. const int MAXLOG = 18;
  7.  
  8. int n, m;
  9. vector<pair<int,int>> adj[MAXN+1];
  10. int parent_[MAXN+1], depth[MAXN+1];
  11. int up[MAXN+1][MAXLOG];
  12. int tin[MAXN+1], tout[MAXN+1], timer = 0;
  13.  
  14. ll net[MAXN+1];    // your “difference” array
  15. ll res[MAXN+1];
  16.  
  17. void dfs1(int u, int p, int d){
  18.     parent_[u] = p;
  19.     depth[u]  = d;
  20.     tin[u]    = ++timer;
  21.     for(auto &e: adj[u]){
  22.         int v = e.first;
  23.         if(v == p) continue;
  24.         dfs1(v, u, d+1);
  25.     }
  26.     tout[u] = timer;
  27. }
  28.  
  29. int lca(int a, int b){
  30.     if(depth[a] < depth[b]) swap(a,b);
  31.     int diff = depth[a] - depth[b];
  32.     for(int j = 0; j < MAXLOG; j++){
  33.         if(diff & (1<<j)) a = up[a][j];
  34.     }
  35.     if(a == b) return a;
  36.     for(int j = MAXLOG-1; j >= 0; j--){
  37.         if(up[a][j] != up[b][j]){
  38.             a = up[a][j];
  39.             b = up[b][j];
  40.         }
  41.     }
  42.     return parent_[a];
  43. }
  44.  
  45. // the second DFS to accumulate your net[] into res[] along the tree
  46. void dfs2(int u, int p, ll acc){
  47.     acc += net[u];
  48.     for(auto &e: adj[u]){
  49.         int v = e.first, idx = e.second;
  50.         if(v == p) continue;
  51.         res[idx] = acc;
  52.         dfs2(v, u, acc);
  53.     }
  54. }
  55.  
  56. int main(){
  57.     ios::sync_with_stdio(false);
  58.     cin.tie(nullptr);
  59.  
  60.     cin >> n;
  61.     for(int i = 0; i < n-1; i++){
  62.         int a,b;
  63.         cin >> a >> b;
  64.         adj[a].push_back({b,i});
  65.         adj[b].push_back({a,i});
  66.     }
  67.  
  68.     // 1) Root at 1, get parent_ and depth and tin/tout
  69.     dfs1(1, 0, 0);
  70.  
  71.     // 2) Build up[v][j]
  72.     for(int v = 1; v <= n; v++){
  73.         up[v][0] = parent_[v];
  74.     }
  75.     for(int j = 1; j < MAXLOG; j++){
  76.         for(int v = 1; v <= n; v++){
  77.             int w = up[v][j-1];
  78.             up[v][j] = w ? up[w][j-1] : 0;
  79.         }
  80.     }
  81.  
  82.     // 3) Read m queries and do the net[] difference trick
  83.     cin >> m;
  84.     while(m--){
  85.         int a,b;
  86.         cin >> a >> b;
  87.         int c = lca(a,b);
  88.         net[c]++;
  89.         if(c==a) {
  90.             net[b]--;
  91.         } else if(c==b){
  92.             net[a]--;
  93.         } else {
  94.             net[a]--;
  95.             net[b]--;
  96.         }
  97.     }
  98.  
  99.     // 4) Propagate net[] to res[] via dfs2
  100.     dfs2(1,0,0LL);
  101.  
  102.     // 5) Output the edge results
  103.     for(int i = 0; i < n-1; i++){
  104.         cout << res[i] << "\n";
  105.     }
  106.     return 0;
  107. }
  108.  
Success #stdin #stdout 0.01s 7176KB
comments (?)
stdin
copy 
5
1 2
1 3
2 4
2 5
2
1 4
3 5
stdout
copy 
2
2
2
2
https://ideone.com/1BeLDj
language:
C++ (gcc 8.3)
created:
9 days 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!