Advertisement
Guest User

Untitled

a guest
Dec 14th, 2019
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 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