fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int mx=2e5+5;
  4. int n, m;
  5. vector<int> adj[mx];
  6. int up[mx][20], dep[mx];
  7. int val[mx]; // Mảng hiệu
  8.  
  9. void dfs_lca(int u, int p) {
  10.     dep[u] = dep[p] + 1;
  11.     up[u][0] = p;
  12.     for(int i=1; i<20; ++i)
  13.         up[u][i] = up[up[u][i-1]][i-1];
  14.  
  15.     for(int v : adj[u]) {
  16.         if(v != p) dfs_lca(v, u);
  17.     }
  18. }
  19.  
  20. int lca(int u, int v) {
  21.     if(dep[u] < dep[v]) swap(u, v);
  22.     for(int i=19; i>=0; --i) {
  23.         if(dep[u] - (1<<i) >= dep[v]) 
  24.             u = up[u][i];
  25.     }
  26.     if(u == v) return u;
  27.     for(int i=19; i>=0; --i) {
  28.         if(up[u][i] != up[v][i]) {
  29.             u = up[u][i];
  30.             v = up[v][i];
  31.         }
  32.     }
  33.     return up[u][0];
  34. }
  35.  
  36. // DFS thứ 2 để cộng dồn từ dưới lên
  37. void dfs_sum(int u, int p) {
  38.     for(int v : adj[u]) {
  39.         if(v != p) {
  40.             dfs_sum(v, u);
  41.             val[u] += val[v]; // Cộng dồn từ con lên cha
  42.         }
  43.     }
  44. }
  45.  
  46. int main()
  47. {
  48.     cin.tie(0)->sync_with_stdio(0);
  49.     if(fopen("Counting_Paths.inp","r"))
  50.     {
  51.         freopen("Counting_Paths.inp","r",stdin);
  52.         freopen("Counting_Paths.out","w",stdout);
  53.     }
  54.  
  55.     cin >> n >> m;
  56.     for(int i=1; i<n; ++i) {
  57.         int u, v;
  58.         cin >> u >> v;
  59.         adj[u].push_back(v);
  60.         adj[v].push_back(u);
  61.     }
  62.  
  63.     dfs_lca(1, 0);
  64.  
  65.     while(m--) {
  66.         int a, b;
  67.         cin >> a >> b;
  68.         int p = lca(a, b);
  69.  
  70.         // Công thức mảng hiệu trên cây
  71.         val[a]++;
  72.         val[b]++;
  73.         val[p]--;
  74.         if(up[p][0] != 0) val[up[p][0]]--; // Trừ ở bố của LCA
  75.     }
  76.  
  77.     dfs_sum(1, 0);
  78.  
  79.     for(int i=1; i<=n; ++i) cout << val[i] << ' ';
  80.     return 0;
  81. }
  82.  
Success #stdin #stdout 0.01s 11676KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0DGX9A
language:
C++14 (gcc 8.3)
created:
5 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!