fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fi first
  4. #define se second
  5. #define ll long long
  6. #define all(x) (x).begin(), (x).end()
  7. #define MASK(i) (1LL<<(i))
  8. #define BIT(i,n) (((n)>>(i)) & 1LL)
  9. #define MIN_HIGH(x, y) (h[x] < h[y] ? (x) : (y));
  10.  
  11. template <class X, class Y>
  12.     bool minimize(X& x, const Y& y)
  13.     {
  14.         if(x > y){
  15.             x = y;
  16.             return 1;
  17.         }
  18.         return 0;
  19.     }
  20.  
  21. template <class X, class Y>
  22.     bool maximize(X& x, const Y& y)
  23.     {
  24.         if(x < y){
  25.             x = y;
  26.             return 1;
  27.         }
  28.         return 0;
  29.     }
  30.  
  31. const int N = 1e3 + 5;
  32. const int LOG = 10;
  33.  
  34. int n, q, nodes[N << 1], d[N], pos[N], h[N], cnt = 0, minH[LOG + 2][N << 1];
  35. vector<pair<int, int>> adj[N];
  36.  
  37. void dfs(int x, int p)
  38. {
  39.     nodes[++cnt] = x;
  40.     pos[x] = cnt;
  41.     for(const auto& y : adj[x]) if(y.fi != p) {
  42.         d[y.fi] = d[x] + y.se;
  43.         h[y.fi] = h[x] + 1;
  44.         dfs(y.fi, x);
  45.         nodes[++cnt] = x;
  46.     }
  47. }
  48.  
  49. int lca(int x, int y)
  50. {
  51.     int px = pos[x], py = pos[y];
  52.     if(px > py) swap(px, py);
  53.  
  54.     int k = 31 - __builtin_clz(py - px + 1);
  55.     return MIN_HIGH(minH[k][px], minH[k][py - MASK(k) + 1]);
  56. }
  57.  
  58. void process()
  59. {
  60.     cin >> n >> q;
  61.     for(int i = 1; i < n; ++i){
  62.         int u, v, w; cin >> u >> v >> w;
  63.         adj[u].push_back({v, w});
  64.         adj[v].push_back({u, w});
  65.     }
  66.  
  67.     dfs(1, -1);
  68.  
  69.     for(int i = 1; i <= cnt; ++i)
  70.         minH[0][i] = nodes[i];
  71.     for(int j = 1; j <= LOG; ++j)
  72.         for(int i = 1; i + MASK(j) - 1 <= cnt; ++i)
  73.             minH[j][i] = MIN_HIGH(minH[j - 1][i], minH[j - 1][i + MASK(j - 1)]);
  74.  
  75.     while(q--){
  76.         int x, y; cin >> x >> y;
  77.         cout << d[x] + d[y] - 2 * d[lca(x, y)] << "\n";
  78.     }
  79. }
  80.  
  81. int main()
  82. {
  83.     ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  84.     #define file "thieufilethinguhetcuu"
  85.     if(fopen(file".inp","r")){
  86.         freopen(file".inp","r",stdin);
  87.         freopen(file".out","w",stdout);
  88.     }
  89.     int _ = 1;
  90. //    cin >> _;
  91.     while(_--){
  92.         process();
  93.     }
  94.     return 0;
  95. }
  96.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mDm7gE
language:
C++14 (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!