fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FNAME ""
  3. using namespace std;
  4. typedef long long ll;
  5. const int MAXN = (int)1001;
  6. const int LIM = (int)1e5 + 1;
  7. const long long MOD = (long long)1e13 + 15092007;
  8. #define xd '\n'
  9. #define pii pair<int, int>
  10. #define pll pair<long long, long long>
  11. #define pli pair<long long, int>
  12. #define fi first
  13. #define se second
  14. const long long base = (long long)256;
  15. const int INF = (int)1e8;
  16. template<class X, class Y> bool minimize(X &a, Y b) {if(a>b){a=b;return true;}return false;};
  17. template<class X, class Y> bool maximize(X &a, Y b) {if(a<b){a=b;return true;}return false;};
  18. const int LOG = 12;
  19.  
  20. void HuuThien() {
  21.     ios_base::sync_with_stdio(0);
  22.     cin.tie(0); cout.tie(0);
  23.     if (fopen(FNAME".inp", "r")) {
  24.         freopen(FNAME".inp", "r", stdin);
  25.         freopen(FNAME".out", "w", stdout);
  26.     }
  27. }
  28.  
  29. int n, q;
  30. long long depth[MAXN];
  31. int up[MAXN][LOG + 1], high[MAXN];
  32. vector<pair<int, int>> adj[MAXN];
  33.  
  34. void dfs(int u) {
  35.     for(pair<int, int> e : adj[u]) {
  36.         int v = e.first, w = e.second;
  37.         if(v != up[u][0]) {
  38.             depth[v] = depth[u] + w;
  39.             high[v] = high[u] + 1;
  40.             up[v][0] = u;
  41.             dfs(v);
  42.         }
  43.     }
  44. }
  45.  
  46. void Init() {
  47.     cin >> n >> q;
  48.     for(int i = 1; i <= n - 1; i++) {
  49.         int u, v, w;
  50.         cin >> u >> v >> w;
  51.         adj[u].push_back({v, w});
  52.         adj[v].push_back({u, w});
  53.     }
  54.  
  55.     up[1][0] = 0;
  56.     high[1] = 0;
  57.     depth[1] = 0;
  58.     high[0] = -1;
  59.     dfs(1);
  60.  
  61.     for(int j = 1; j >= LOG; j++) {
  62.         for(int i = 1; i <= n ; i++) {
  63.             up[i][j] = up[up[i][j - 1]][j - 1];
  64.         } 
  65.     }
  66. }
  67.  
  68. int lca(int u, int v) {
  69.     if(high[u] < high[v]) return lca(v, u);
  70.  
  71.     for(int i = LOG; i >= 0 ; i--) {
  72.         if(high[up[u][i]] >= high[v]) {
  73.             u = up[u][i];
  74.         }
  75.     }
  76.  
  77.     if(u == v) return u;
  78.  
  79.     for(int i = LOG; i >= 0 ; i--) {
  80.         if(up[u][i] != up[v][i]) {
  81.             u = up[u][i];
  82.             v = up[v][i];
  83.         }
  84.     }
  85.  
  86.     return up[u][0];
  87. }
  88.  
  89. void Solve() {
  90.     while(q--) {
  91.         int u, v;
  92.         cin >> u >> v;
  93.         int cnode = lca(u, v);
  94.         cout << depth[u] + depth[v] - 2 * depth[cnode] << xd;
  95.     }
  96. }
  97.  
  98. signed main() {
  99.     HuuThien();
  100.     Init();
  101.     Solve();
  102.     return 0;
  103. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KzOkec
language:
C++ (gcc 8.3)
created:
2 hours 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!