結果
問題 | No.898 tri-βutree |
ユーザー | alexara1123 |
提出日時 | 2019-11-13 12:18:28 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 339 ms / 4,000 ms |
コード長 | 4,289 bytes |
コンパイル時間 | 1,393 ms |
コンパイル使用メモリ | 108,204 KB |
実行使用メモリ | 20,408 KB |
最終ジャッジ日時 | 2023-08-08 16:28:31 |
合計ジャッジ時間 | 8,490 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 212 ms
20,408 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 325 ms
17,652 KB |
testcase_08 | AC | 321 ms
17,460 KB |
testcase_09 | AC | 325 ms
17,568 KB |
testcase_10 | AC | 316 ms
17,388 KB |
testcase_11 | AC | 322 ms
17,496 KB |
testcase_12 | AC | 321 ms
17,504 KB |
testcase_13 | AC | 339 ms
17,424 KB |
testcase_14 | AC | 324 ms
17,516 KB |
testcase_15 | AC | 315 ms
17,404 KB |
testcase_16 | AC | 323 ms
17,504 KB |
testcase_17 | AC | 322 ms
17,460 KB |
testcase_18 | AC | 325 ms
17,496 KB |
testcase_19 | AC | 328 ms
17,364 KB |
testcase_20 | AC | 319 ms
17,392 KB |
testcase_21 | AC | 318 ms
17,460 KB |
ソースコード
#include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <string> #include <cstring> #include <queue> #include <set> #include <unordered_set> #include <unordered_map> #include <map> #include <numeric> #include <functional> #include <cmath> #include <cassert> #include <string> #include <iostream> using namespace std; typedef long long ll; typedef pair<int, int> P; typedef pair<ll, ll> PL; const ll MOD = 1000000007; const int mod = 1000000007; ll INF = 1LL << 60; template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; } template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; } template <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; } template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; } template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } template <typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }; #define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl; template <typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val) { fill((T *)array, (T *)(array + N), val); } struct LCA { int n, h; vector<vector<int>> par; vector<vector<pair<int, int>>> v; vector<ll> depth, dis; LCA(int sz) : n(sz), v(n), depth(n), dis(n) { h = 1; while ((1 << h) < n) h++; par.assign(h, vector<int>(n, -1)); } void add_edge(int x, int y, int z) { v[x].push_back({y, z}); v[y].push_back({x, z}); } void dfs(int x, int p, int d, ll di) { par[0][x] = p; depth[x] = d; dis[x] = di; for (auto to : v[x]) if (to.first != p) dfs(to.first, x, d + 1, di + to.second); } void build() { dfs(0, -1, 0, 0); for(int i=0; i < h-1; i++) { for(int j=0; j < n; j++) { if (par[i][j] < 0) par[i + 1][j] = -1; else par[i + 1][j] = par[i][par[i][j]]; } } } int lca(int u, int v) { if (depth[u] > depth[v]) swap(u, v); for(int i=0; i < h; i++) if ((depth[v] - depth[u]) >> i & 1) v = par[i][v]; if (u == v) return u; for (int i = h - 1; i >= 0; i--) { if (par[i][u] != par[i][v]) { u = par[i][u]; v = par[i][v]; } } return par[0][u]; } ll dist(int u, int v) { return dis[u] + dis[v] - 2 * dis[lca(u, v)]; } }; int solve() { ll n; cin >> n; LCA lca(n); for(int i=0; i < n-1; i++){ ll u, v, w; cin >> u >> v >> w; lca.add_edge(u, v, w); } lca.build(); ll q; cin >> q; while (q--) { ll a,b,c; cin >> a >> b >> c; cout << (lca.dist(a,b) + lca.dist(b,c) + lca.dist(c,a))/2 << endl; } return 0; } int main() { //cout.precision(10) ios::sync_with_stdio(false); cin.tie(0); solve(); }