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 LOG  = 18;
  7.  
  8. int n, k;
  9. vector<pair<int,int>> adj[MAXN+1];
  10. int parent_[MAXN+1], depth[MAXN+1];
  11. int up[MAXN+1][LOG];
  12. ll net[MAXN+1], sumv[MAXN+1];
  13. int res[MAXN+1];  // res[edge_id]
  14.  
  15. // 1) DFS to compute parent_, depth, tin/tout if needed, but here just parent/depth
  16. void dfs1(int u,int p){
  17.     parent_[u]=p;
  18.     for(auto &e:adj[u]){
  19.         int v=e.first, id=e.second;
  20.         if(v==p) continue;
  21.         depth[v]=depth[u]+1;
  22.         dfs1(v,u);
  23.     }
  24. }
  25.  
  26. // 2) LCA via binary lifting
  27. int lca(int a,int b){
  28.     if(depth[a]<depth[b]) swap(a,b);
  29.     int diff=depth[a]-depth[b];
  30.     for(int j=0;j<LOG;j++){
  31.         if(diff&(1<<j)) a=up[a][j];
  32.     }
  33.     if(a==b) return a;
  34.     for(int j=LOG-1;j>=0;j--){
  35.         if(up[a][j]!=up[b][j]){
  36.             a=up[a][j];
  37.             b=up[b][j];
  38.         }
  39.     }
  40.     return parent_[a];
  41. }
  42.  
  43. // 3) DFS to accumulate net[] into sumv[], and record edge results
  44. void dfs2(int u,int p){
  45.     sumv[u] = net[u];
  46.     for(auto &e:adj[u]){
  47.         int v=e.first, id=e.second;
  48.         if(v==p) continue;
  49.         dfs2(v,u);
  50.         sumv[u] += sumv[v];
  51.         res[id] = sumv[v]; // edge u-v (id) is used sumv[v] times
  52.     }
  53. }
  54.  
  55. int main(){
  56.     ios::sync_with_stdio(false);
  57.     cin.tie(nullptr);
  58.  
  59.     cin>>n;
  60.     for(int i=0;i<n-1;i++){
  61.         int u,v;
  62.         cin>>u>>v;
  63.         adj[u].push_back({v,i});
  64.         adj[v].push_back({u,i});
  65.     }
  66.  
  67.     // build parent_ and depth by rooting at 1
  68.     depth[1]=0;
  69.     dfs1(1,0);
  70.  
  71.     // build up table: up[v][0] = parent_[v]
  72.     for(int v=1;v<=n;v++){
  73.         up[v][0] = parent_[v];
  74.     }
  75.     for(int j=1;j<LOG;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.     // read k queries, do net-difference
  83.     cin>>k;
  84.     while(k--){
  85.         int a,b;
  86.         cin>>a>>b;
  87.         int c = lca(a,b);
  88.         net[a] += 1;
  89.         net[b] += 1;
  90.         net[c] -= 2;
  91.     }
  92.  
  93.     // accumulate and fill res[]
  94.     dfs2(1,0);
  95.  
  96.     // output edge answers in input order
  97.     for(int i=0;i<n-1;i++){
  98.         cout<<res[i]<<"\n";
  99.     }
  100.     return 0;
  101. }
  102.  
Success #stdin #stdout 0.01s 9432KB
comments (?)
stdin
copy 
5
1 2
1 3
2 4
2 5
2
1 4
3 5
stdout
copy 
2
1
1
1
https://ideone.com/ElShgj
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!