Advertisement
Guest User

Untitled

a guest
Dec 14th, 2019
204
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.85 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. #define FR(i, n) for(int i = 0; i < (n); i++)
  6. #define FOR(i, l, r) for(int i = (l); i < (r); i++)
  7. #define all(x) x.begin(), x.end()
  8. #define fs first
  9. #define sc second
  10.  
  11. using namespace std;
  12.  
  13. const int N = 5e4 + 10;
  14. int n, k;
  15. vector<pair<int, int>> g[N];
  16. int pr[N][17], gl[N], dist_0[N];
  17.  
  18. void count_pr(int vx, int p1) {
  19.     FR(i, 17) {
  20.         pr[vx][i] = p1;
  21.         p1 = pr[p1][i];
  22.     }
  23. }
  24.  
  25. void dfs_pr_lv(int vx, int lv, int p1, int dt) {
  26.     gl[vx] = lv;
  27.     dist_0[vx] = dt;
  28.     count_pr(vx, p1);
  29.     for(auto i : g[vx]) {
  30.         if(gl[i.fs] == 0) {
  31.             dfs_pr_lv(i.fs, lv+1, vx, dt + i.sc);
  32.         }
  33.     }
  34. }
  35.  
  36. int find_vx(int va, int lv) {
  37.     int k2 = 17;
  38.     while(k2 != 0) {
  39.         if(gl[pr[va][k2]] < lv) {
  40.             k2--;
  41.         } else {
  42.             va = pr[va][k2];
  43.         }
  44.     }
  45.     return pr[va][0];
  46. }
  47.  
  48. int lca(int bg, int ed) {
  49.     if(gl[bg] > gl[ed]) swap(bg, ed);
  50.     //cout << '(' << endl;
  51.     ed = find_vx(ed, gl[bg]);
  52.     //cout << bg << ' ' << ed << endl;
  53.     if(bg == ed) return bg;
  54.     int k2 = 17;
  55.     while(k2 != 0) {
  56.         if(pr[bg][k2] == pr[ed][k2]) {
  57.             k2--;
  58.         } else {
  59.             bg = pr[bg][k2];
  60.             ed = pr[ed][k2];
  61.         }
  62.     }
  63.     return pr[bg][0];
  64. }
  65.  
  66. int dist(int bg, int ed) {
  67.     int cm_vx = lca(bg, ed);
  68.     return dist_0[bg] + dist_0[ed] - 2 * dist_0[cm_vx];
  69. }
  70.  
  71. signed main() {
  72.     ios_base::sync_with_stdio(0);
  73.     cin.tie(0); cout.tie(0);
  74.     cin >> n;
  75.     FR(i, n-1) {
  76.         int a, b, c;
  77.         cin >> a >> b >> c;
  78.         g[a].push_back({b, c});
  79.         g[b].push_back({a, c});
  80.     }
  81.     cin >> k;
  82.    
  83.     dfs_pr_lv(0, 1, 0, 0);
  84.    
  85.     FR(i, k) {
  86.         int b, e;
  87.         cin >> b >> e;
  88.         cout << dist(b, e) << '\n';
  89.     }
  90.    
  91.     return 0;
  92. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement