結果
問題 | No.898 tri-βutree |
ユーザー |
|
提出日時 | 2019-09-16 23:48:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 304 ms / 4,000 ms |
コード長 | 2,538 bytes |
コンパイル時間 | 2,218 ms |
コンパイル使用メモリ | 187,544 KB |
実行使用メモリ | 28,952 KB |
最終ジャッジ日時 | 2024-11-08 21:37:40 |
合計ジャッジ時間 | 9,398 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std::literals::string_literals;using i64 = long long;using std::cout;using std::endl;using std::cin;template<typename T>std::vector<T> make_v(size_t a){return std::vector<T>(a);}template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}struct LowestCommonAncestor{std::vector<std::vector<int>> g, parent;std::vector<int> depth;bool built = false;int N;const int logN = 20;LowestCommonAncestor(int n) : N(n) {g.resize(N);parent.resize(logN, std::vector<int>(N));depth.resize(N);}void add_edge(int u, int v){g[u].push_back(v);g[v].push_back(u);}void dfs(int v, int par = -1, int d = 0){parent[0][v] = par;depth[v] = d;for(auto e:g[v]){if(e == par) continue;dfs(e, v, d + 1);}}void build(){dfs(0);for(int k = 0; k < logN - 1; k++){for(int i = 0; i < N; i++){if(parent[k][i] < 0) parent[k + 1][i] = -1;else parent[k + 1][i] = parent[k][parent[k][i]];}}}int get(int u, int v){if(!built) build(); built = true;if(depth[u] > depth[v]) std::swap(u, v);for(int k = 0; k < logN; k++){if(((depth[v] - depth[u]) >> k) & 1){v = parent[k][v];}}if(u == v) return u;for(int k = logN - 1; k >= 0; k--){if(parent[k][u] == parent[k][v]) continue;u = parent[k][u];v = parent[k][v];}return parent[0][u];}};int main() {// inputint n; scanf("%d", &n);assert(1 <= n and n <= (int)1e5);LowestCommonAncestor lca(n);std::vector<std::vector<std::pair<int, i64>>> g(n);for(int i = 0; i < n - 1; i++) {int a, b, c; scanf("%d%d%d", &a, &b, &c);assert(0 <= a and a < n);assert(0 <= b and b < n);assert(1 <= c and c <= (int)1e9);g[a].push_back({b, c});g[b].push_back({a, c});lca.add_edge(a, b);}lca.build();// solvestd::vector<i64> dist(n);auto dfs = [&](auto && dfs, int v, int par) -> void {for(auto e: g[v]) {if(e.first == par) continue;dist[e.first] = dist[v] + e.second;dfs(dfs, e.first, v);}};dfs(dfs, 0, -1);auto calc = [&lca, dist](const int & x, const int & y) -> i64 {return dist[x] + dist[y] - 2LL * dist[lca.get(x, y)];};int q; scanf("%d", &q);while(q--) {int x, y, z; scanf("%d%d%d", &x, &y, &z);assert(0 <= x and x < n);assert(0 <= y and y < n);assert(0 <= z and z < n);printf("%lld\n", (calc(x, y) + calc(y, z) + calc(z, x)) >> 1);}return 0;}