結果
問題 | No.898 tri-βutree |
ユーザー | leaf_1415 |
提出日時 | 2019-10-04 21:37:36 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,473 bytes |
コンパイル時間 | 740 ms |
コンパイル使用メモリ | 61,404 KB |
実行使用メモリ | 26,112 KB |
最終ジャッジ日時 | 2024-04-26 08:28:11 |
合計ジャッジ時間 | 5,249 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | AC | 4 ms
5,760 KB |
testcase_02 | AC | 4 ms
5,760 KB |
testcase_03 | AC | 4 ms
5,760 KB |
testcase_04 | AC | 4 ms
5,760 KB |
testcase_05 | AC | 4 ms
5,632 KB |
testcase_06 | AC | 4 ms
5,760 KB |
testcase_07 | AC | 173 ms
18,688 KB |
testcase_08 | AC | 160 ms
18,688 KB |
testcase_09 | AC | 150 ms
18,688 KB |
testcase_10 | AC | 154 ms
18,688 KB |
testcase_11 | AC | 164 ms
18,688 KB |
testcase_12 | AC | 161 ms
18,688 KB |
testcase_13 | AC | 160 ms
18,688 KB |
testcase_14 | AC | 150 ms
18,688 KB |
testcase_15 | AC | 148 ms
18,688 KB |
testcase_16 | AC | 149 ms
18,688 KB |
testcase_17 | AC | 154 ms
18,688 KB |
testcase_18 | AC | 148 ms
18,816 KB |
testcase_19 | AC | 148 ms
18,688 KB |
testcase_20 | AC | 149 ms
18,688 KB |
testcase_21 | AC | 152 ms
18,688 KB |
ソースコード
#include <iostream> #include <vector> #define llint long long using namespace std; struct edge{ llint to, cost; edge(){} edge(llint a, llint b){ to = a, cost = b; } }; llint n, Q; vector<edge> G[100005]; int Prev[100005][17]; int depth[100005]; llint dist[100005]; int getLCA(int u, int v){ int x = u, y = v; if(depth[y] > depth[x]) swap(x, y); for(int i = 16; i >= 0; i--){ if(depth[x] - (1<<i) >= depth[y]) x = Prev[x][i]; } if(x == y) return x; for(int i = 16; i >= 0; i--){ if(Prev[x][i] != Prev[y][i]){ x = Prev[x][i]; y = Prev[y][i]; } } x = Prev[x][0]; return x; } void dfs(int v, int p, int d, llint dst) { Prev[v][0] = p, depth[v] = d, dist[v] = dst; for(int i = 0; i < G[v].size(); i++){ if(G[v][i].to == p) continue; dfs(G[v][i].to, v, d+1, dst + G[v][i].cost); } } llint calc(llint s, llint t) { llint lca = getLCA(s, t); return dist[s] + dist[t] - 2 * dist[lca]; } int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n; llint u, v, w; for(int i = 1; i <= n-1; i++){ cin >> u >> v >> w; u++, v++; G[u].push_back(edge(v, w)); G[v].push_back(edge(u, w)); } dfs(1, -1, 0, 0); for(int i = 1; i < 16; i++){ for(int j = 1; j <= n; j++){ Prev[j][i] = Prev[Prev[j][i-1]][i-1]; } } cin >> Q; llint x, y, z; for(int q = 0; q < Q; q++){ cin >> x >> y >> z; x++, y++, z++; llint ans = calc(x, y) + calc(y, z) + calc(z, x); cout << ans / 2 << "\n"; } flush(cout); return 0; }