結果
問題 | No.898 tri-βutree |
ユーザー | みずくらげ |
提出日時 | 2019-10-05 01:45:41 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 426 ms / 4,000 ms |
コード長 | 1,890 bytes |
コンパイル時間 | 1,290 ms |
コンパイル使用メモリ | 118,100 KB |
実行使用メモリ | 23,908 KB |
最終ジャッジ日時 | 2024-11-08 22:41:46 |
合計ジャッジ時間 | 9,916 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 266 ms
23,908 KB |
testcase_01 | AC | 3 ms
5,888 KB |
testcase_02 | AC | 3 ms
5,888 KB |
testcase_03 | AC | 3 ms
5,888 KB |
testcase_04 | AC | 3 ms
5,888 KB |
testcase_05 | AC | 4 ms
5,888 KB |
testcase_06 | AC | 3 ms
5,888 KB |
testcase_07 | AC | 406 ms
18,816 KB |
testcase_08 | AC | 412 ms
18,688 KB |
testcase_09 | AC | 421 ms
18,688 KB |
testcase_10 | AC | 425 ms
18,816 KB |
testcase_11 | AC | 412 ms
18,816 KB |
testcase_12 | AC | 412 ms
18,816 KB |
testcase_13 | AC | 407 ms
18,688 KB |
testcase_14 | AC | 407 ms
18,816 KB |
testcase_15 | AC | 406 ms
18,688 KB |
testcase_16 | AC | 413 ms
18,688 KB |
testcase_17 | AC | 411 ms
18,688 KB |
testcase_18 | AC | 414 ms
18,688 KB |
testcase_19 | AC | 426 ms
18,688 KB |
testcase_20 | AC | 408 ms
18,688 KB |
testcase_21 | AC | 416 ms
18,688 KB |
ソースコード
#include <iostream> #include <vector> #include <string> #include <cstring> #include <algorithm> #include <cmath> #include <set> #include <map> #include <queue> #include <iomanip> #include <cassert> #include <random> #include <tuple> #define rep(i,n) for (int i = 0; i < (n); ++i) using namespace std; typedef long long ll; typedef pair<int, int> P; const int INF = 1001001001; struct edge { int to, cost; }; vector<edge> g[100100]; vector<int> depth; vector<ll> cost; vector<vector<int> > parent; int n; void dfs(int v, int p=-1, int d=0) { depth[v] = d; parent[0][v] = p; for (auto e: g[v]) { if (e.to == p) continue; cost[e.to] = cost[v] + e.cost; dfs(e.to, v, d+1); } } void init(int root=0) { depth.resize(n, 0); cost.resize(n, 0); parent.resize(20, vector<int>(n, 0)); dfs(root); rep(k, 19) { rep(v, n) { if (parent[k][v] < 0) parent[k+1][v] = -1; else parent[k+1][v] = parent[k][parent[k][v]]; } } } int lca(int u, int v) { if (depth[u] > depth[v]) swap(u, v); rep(k, 20) { if (((depth[v] - depth[u]) >> k) & 1) v = parent[k][v]; } if (u == v) return u; for (int k = 19; k >= 0; k--) { if (parent[k][u] == parent[k][v]) continue; u = parent[k][u]; v = parent[k][v]; } return parent[0][v]; } int main() { cin >> n; rep(i, n-1) { int u, v, w; cin >> u >> v >> w; edge e1 = {v, w}; g[u].push_back(e1); edge e2 = {u, w}; g[v].push_back(e2); } init(); int q; cin >> q; rep(i, q) { int x, y, z; cin >> x >> y >> z; int xy = lca(x, y); int yz = lca(y, z); int zx = lca(z, x); cout << (cost[x] + cost[y] + cost[z] - (cost[xy] + cost[yz] + cost[zx])) << endl; } return 0; }