結果
問題 | No.898 tri-βutree |
ユーザー | tonegawa |
提出日時 | 2020-02-06 00:55:45 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 725 ms / 4,000 ms |
コード長 | 2,163 bytes |
コンパイル時間 | 1,095 ms |
コンパイル使用メモリ | 105,076 KB |
実行使用メモリ | 189,408 KB |
最終ジャッジ日時 | 2023-08-08 16:38:06 |
合計ジャッジ時間 | 15,567 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 425 ms
189,408 KB |
testcase_01 | AC | 118 ms
174,900 KB |
testcase_02 | AC | 117 ms
174,900 KB |
testcase_03 | AC | 118 ms
175,212 KB |
testcase_04 | AC | 118 ms
174,952 KB |
testcase_05 | AC | 118 ms
175,028 KB |
testcase_06 | AC | 119 ms
174,964 KB |
testcase_07 | AC | 704 ms
183,608 KB |
testcase_08 | AC | 708 ms
183,600 KB |
testcase_09 | AC | 696 ms
183,504 KB |
testcase_10 | AC | 716 ms
183,676 KB |
testcase_11 | AC | 723 ms
183,532 KB |
testcase_12 | AC | 725 ms
183,660 KB |
testcase_13 | AC | 700 ms
183,660 KB |
testcase_14 | AC | 711 ms
183,532 KB |
testcase_15 | AC | 698 ms
183,520 KB |
testcase_16 | AC | 704 ms
183,528 KB |
testcase_17 | AC | 704 ms
183,604 KB |
testcase_18 | AC | 690 ms
183,784 KB |
testcase_19 | AC | 713 ms
183,468 KB |
testcase_20 | AC | 711 ms
183,520 KB |
testcase_21 | AC | 714 ms
183,664 KB |
ソースコード
#include <iostream> #include <string> #include <vector> #include <deque> #include <queue> #include <algorithm> #include <set> #include <map> #include <bitset> #include <cmath> #include <functional> #include <iomanip> #define vll vector<ll> #define vvv vector<vvl> #define vvi vector<vector<int> > #define vvl vector<vector<ll> > #define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c)) #define vvvl(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d))); #define rep(c, a, b) for(ll c=a;c<b;c++) #define re(c, b) for(ll c=0;c<b;c++) #define all(obj) (obj).begin(), (obj).end() typedef long long int ll; typedef long double ld; typedef __int128_t lll; using namespace std; const int MAX_V = 1000001; vvi G = vv(MAX_V, 0, 0, int); int root; int parent[30][MAX_V]; vector<int> depth(MAX_V); void dfs(int v, int p, int d){ parent[0][v] = p, depth[v] = d; for(int i=0;i<G[v].size();i++) if(G[v][i] != p) dfs(G[v][i], v, d+1); } void init(){ dfs(root, -1, 0); for(int k=0;k+1<30;k++){ for(int v=0;v<MAX_V;v++){ 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); for(int k=0;k<30;k++)if((depth[v]-depth[u])>>k & 1) v = parent[k][v]; if(u==v) return u; for(int k=30-1;k>=0;k--){ if(parent[k][u] != parent[k][v]){ u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } struct edge{ll to, cost;}; vector<vector<edge>> T(MAX_V, vector<edge>(0)); vll d(MAX_V, 0); void calc(ll now, ll from, ll dist){ d[now] = dist; for(int i=0;i<T[now].size();i++){ if(T[now][i].to==from) continue; calc(T[now][i].to, now, dist + T[now][i].cost); } } ll f(ll a, ll b){ return d[a] + d[b] - 2*d[lca(a, b)]; } int main(int argc, char const *argv[]) { ll a, b, c, n;std::cin >> n; re(i, n-1){ std::cin >> a >> b >> c; G[a].push_back(b);G[b].push_back(a); T[a].push_back(edge{b, c});T[b].push_back(edge{a, c}); } root = 0; init();calc(0, -1, 0); ll q;std::cin >> q; re(i, q){ std::cin >> a >> b >> c; std::cout << (f(a, b) + f(b, c) + f(a, c))/2 << '\n'; } return 0; }