結果
問題 | No.898 tri-βutree |
ユーザー |
![]() |
提出日時 | 2019-10-04 21:53:53 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 832 ms / 4,000 ms |
コード長 | 1,636 bytes |
コンパイル時間 | 721 ms |
コンパイル使用メモリ | 63,768 KB |
実行使用メモリ | 42,588 KB |
最終ジャッジ日時 | 2024-11-08 22:05:15 |
合計ジャッジ時間 | 15,242 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#define int long longusing namespace std;int n;vector<int> et[100000];vector<int> ec[100000];int q;int x[100000], y[100000], z[100000];int parent[100000];int depth[100000];int dist[100000];void dfs(int p, int v, int dep, int dis) {int i;parent[v] = p;depth[v] = dep;dist[v] = dis;for (i = 0; i < et[v].size(); i++) {int nv = et[v][i];if (nv == p) continue;dfs(v, nv, dep + 1, dis + ec[v][i]);}}int parents[20][100000];int lca(int u, int v) {if (depth[u] < depth[v]) {swap(u, v);}int i;int diff = depth[u] - depth[v];for (i = 0; i < 20; i++) {if ((diff >> i) % 2 == 1) {u = parents[i][u];}}for (i = 19; i >= 0; i--) {if (parents[i][u] != parents[i][v]) {u = parents[i][u];v = parents[i][v];}}if (u == v) return u;return parent[u];}int distance(int u, int v) {return dist[u] + dist[v] - 2 * dist[lca(u, v)];}signed main() {int i, j;cin >> n;for (i = 0; i < n - 1; i++) {int u, v, w;cin >> u >> v >> w;et[u].push_back(v);ec[u].push_back(w);et[v].push_back(u);ec[v].push_back(w);}cin >> q;for (i = 0; i < q; i++) {cin >> x[i] >> y[i] >> z[i];}dfs(0, 0, 0, 0);for (i = 0; i < n; i++) {parents[0][i] = parent[i];}for (i = 0; i < 19; i++) {for (j = 0; j < n; j++) {parents[i + 1][j] = parents[i][parents[i][j]];}}for (i = 0; i < q; i++) {int distXY = distance(x[i], y[i]);int distYZ = distance(y[i], z[i]);int distZX = distance(z[i], x[i]);cout << (distXY + distYZ + distZX) / 2 << endl;}return 0;}