結果

問題 No.898 tri-βutree
ユーザー pekempeypekempey
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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';
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0