結果
問題 | No.898 tri-βutree |
ユーザー |
|
提出日時 | 2019-10-04 21:34:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 166 ms / 4,000 ms |
コード長 | 2,770 bytes |
コンパイル時間 | 2,332 ms |
コンパイル使用メモリ | 186,960 KB |
実行使用メモリ | 23,424 KB |
最終ジャッジ日時 | 2024-11-08 21:54:26 |
合計ジャッジ時間 | 6,872 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>#define rep(i, n) for (int i = 0; i < (n); i++)#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)#define rep2(i, l, r) for (int i = (l); i < (r); i++)#define rep2r(i, l, r) for (int i = (r) - 1; i >= (l); i--)#define range(a) a.begin(), a.end()using namespace std;using ll = long long;struct HLD {vector<int> label, parent, head;vector<ll> dep;HLD(const vector<vector<pair<int, ll>>> &g) : label(g.size()), parent(g.size()), head(g.size()), dep(g.size()) {const int n = g.size();vector<int> size(n, 1);auto dfs = [&](auto dfs, int u, int p) -> void {for (auto e : g[u]) if (e.first != p) {dep[e.first] = dep[u] + e.second;dfs(dfs, e.first, u);size[u] += size[e.first];}};dfs(dfs, 0, -1);int k = 0;auto dfs2 = [&](auto dfs, int u, int p, int h) -> void {label[u] = k++;head[u] = h;parent[u] = p;for (auto e : g[u]) if (e.first != p && size[e.first] * 2 > size[u]) dfs(dfs, e.first, u, h);for (auto e : g[u]) if (e.first != p && size[e.first] * 2 <= size[u]) dfs(dfs, e.first, u, e.first);};dfs2(dfs2, 0, -1, 0);}int lca(int u, int v) {for (;;) {if (label[u] > label[v]) swap(u, v);if (head[u] == head[v]) return u;v = parent[head[v]];}}template<class F> void each(int u, int v, F f) {for (;;) {if (label[u] > label[v]) swap(u, v);if (head[u] == head[v]) {f(label[u], label[v]);return;}f(label[head[v]], label[v]);v = parent[head[v]];}}template<class F> void each_edge(int u, int v, F f) {for (;;) {if (label[u] > label[v]) swap(u, v);if (head[u] == head[v]) {if (u != v) f(label[u] + 1, label[v]);return;}f(label[head[v]], label[v]);v = parent[head[v]];}}int operator[](int u) {return label[u];};int common(int a, int b, int c) {for (;;) {if (label[a] < label[b]) swap(a, b);if (label[a] < label[c]) swap(a, c);if (label[b] < label[c]) swap(b, c);if (head[a] == head[b]) return b;a = parent[head[a]];}}ll dist(int u, int v) {return dep[u] + dep[v] - 2 * dep[lca(u, v)];}};int main() {cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(15);int N; cin >> N;vector<vector<pair<int, ll>>> G(N);rep(i, N - 1) {int a, b, c; cin >> a >> b >> c;G[a].emplace_back(b, c);G[b].emplace_back(a, c);}HLD hld(G);int Q; cin >> Q;while (Q--) {int a, b, c; cin >> a >> b >> c;int x = hld.common(a, b, c);cout << hld.dist(a, x) + hld.dist(b, x) + hld.dist(c, x) << '\n';}}