Advertisement
Vince14

/<> 1761 (basic LCA: distance between nodes)

Sep 29th, 2023
110
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.04 KB | Source Code | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <stack>
  10. #include <queue>
  11. #include <deque>
  12. #include <unordered_map>
  13. #include <numeric>
  14. #include <iomanip>
  15. using namespace std;
  16. #define pii pair<int , int>
  17. #define ll long long
  18. #define FAST ios_base::sync_with_stdio(false); cin.tie(NULL)
  19. const long long dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
  20. const long long dl[2] = {1, -1};
  21. const long long MOD = 1000000007;
  22. const long long MAXN = 40005;
  23.  
  24. int N, M;
  25. vector<pii> adj[MAXN]; // node, distance
  26. int dist[MAXN];
  27. int depth[MAXN];
  28. int par[MAXN][22];
  29.  
  30. void make_tree(int c, int p, int dep, int di){
  31.     dist[c] = di;
  32.     depth[c] = dep;
  33.     par[c][0] = p;
  34.     for(auto x : adj[c]){
  35.         if(x.first != p){
  36.             make_tree(x.first, c, dep + 1, di + x.second);
  37.         }
  38.     }
  39. }
  40.  
  41. int LCA (int x, int y){
  42.     if(depth[x] < depth[y]){
  43.         swap(x, y);
  44.     }
  45.     if(depth[x] != depth[y]){
  46.         int k = depth[x] - depth[y];
  47.         for(int i = 0; i <= 20; i++){
  48.             if((k & (1 << i)) != 0){
  49.                 x = par[x][i];
  50.             }
  51.         }
  52.     }
  53.     if(x == y){
  54.         return x;
  55.     }
  56.     for(int i = 20; i >= 0; i--){
  57.         int xx = par[x][i];
  58.         int yy = par[y][i];
  59.         if(xx != yy){
  60.             x = xx;
  61.             y = yy;
  62.         }
  63.     }
  64.     return par[x][0];
  65. }
  66.  
  67.  
  68.  
  69. int main() {
  70.     FAST;
  71.     cin >> N;
  72.     for(int x, y, z, i = 0; i < N - 1; i++){
  73.         cin >> x >> y >> z;
  74.         adj[x].push_back({y, z});
  75.         adj[y].push_back({x, z});
  76.     }
  77.     make_tree(1, 0, 1, 0);
  78.     for(int j = 1; j <= 20; j++){
  79.         for(int i = 2; i <= N; i++){
  80.             par[i][j] = par[par[i][j - 1]][j - 1];
  81.         }
  82.     }
  83.     cin >> M;
  84.     for(int x, y, i = 0; i < M; i++){
  85.         cin >> x >> y;
  86.         int lca = LCA(x, y);
  87.         cout << dist[x] + dist[y] - dist[lca] * 2 << "\n";
  88.     }
  89. }
  90.  
  91. /*
  92. 7
  93. 1 6 13
  94. 6 3 9
  95. 3 5 7
  96. 4 1 3
  97. 2 4 20
  98. 4 7 2
  99. 3
  100. 1 6
  101. 1 4
  102. 2 6
  103.  */
  104.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement