結果
問題 |
No.1094 木登り / Climbing tree
|
ユーザー |
![]() |
提出日時 | 2021-05-21 19:34:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,038 ms / 2,000 ms |
コード長 | 1,983 bytes |
コンパイル時間 | 3,527 ms |
コンパイル使用メモリ | 206,652 KB |
最終ジャッジ日時 | 2025-01-21 14:05:56 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; template<typename T = long long> class lca { int n; vector<vector<pair<int, T> > > edges; vector<int> depth; vector<vector<int> > par; vector<T> dist; void dfs(int v, int p = -1, int d = 0, T l = 0) { par[0][v] = p; depth[v] = d; dist[v] = l; for (auto &[u, w]: edges[v]) { if (u == p) continue; dfs(u, v, d + 1, l + w); } } public: lca(int n): n(n) { edges = vector<vector<pair<int, T> > >(n); depth = vector<int>(n); int m = 1; while ((1<<m) < n) ++m; par = vector<vector<int> >(m, vector<int>(n)); dist = vector<T>(n); } void add_edge(int v, int w, T l = 0) { edges[v].emplace_back(w, l); edges[w].emplace_back(v, l); } void build() { dfs(0); for (int i = 1; i < par.size(); i++) { for (int j = 0; j < n; j++) { par[i][j] = par[i-1][j] == -1 ? -1 : par[i-1][par[i-1][j]]; } } } int get(int v, int w) { if (depth[w] > depth[v]) swap(v, w); int d = depth[v] - depth[w]; for (int i = 0; i < par.size(); i++) { if (d & 1 << i) { v = par[i][v]; } } if (v == w) return v; for (int i = par.size() - 1; i >= 0; i--) { if (par[i][v] != par[i][w]) { v = par[i][v]; w = par[i][w]; } } return par[0][v]; } int get_length(int u, int v) { int w = get(u, v); return depth[u] + depth[v] - 2 * depth[w]; } T get_dist(int u, int v) { int w = get(u, v); return dist[u] + dist[v] - 2 * dist[w]; } }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; lca tree(n); for (int i = 0; i < n-1; i++) { int a, b, c; cin >> a >> b >> c; --a, --b; tree.add_edge(a, b, c); } tree.build(); int q; cin >> q; while (q--) { int s, t; cin >> s >> t; --s, --t; cout << tree.get_dist(s, t) << endl; } return 0; }