結果
問題 | No.898 tri-βutree |
ユーザー | treeone |
提出日時 | 2019-10-04 23:17:58 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,396 bytes |
コンパイル時間 | 2,641 ms |
コンパイル使用メモリ | 233,612 KB |
実行使用メモリ | 84,352 KB |
最終ジャッジ日時 | 2024-10-03 08:49:37 |
合計ジャッジ時間 | 23,377 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | AC | 3 ms
6,820 KB |
testcase_02 | AC | 3 ms
6,820 KB |
testcase_03 | AC | 2 ms
6,816 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | AC | 3 ms
6,816 KB |
testcase_07 | AC | 1,163 ms
82,512 KB |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | AC | 1,152 ms
82,516 KB |
testcase_11 | AC | 1,246 ms
82,628 KB |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | AC | 1,203 ms
82,628 KB |
testcase_17 | AC | 1,212 ms
82,504 KB |
testcase_18 | WA | - |
testcase_19 | AC | 1,197 ms
82,632 KB |
testcase_20 | AC | 1,222 ms
82,640 KB |
testcase_21 | AC | 1,211 ms
82,504 KB |
ソースコード
#include <bits/stdc++.h>#define rep(i, a, n) for(int i = a; i < n; i++)#define int long longusing namespace std;typedef pair<int, int> P;const int mod = 1000000007;const int INF = 1e18;struct LowestCommonAncestor{const int MAX_LOG_V = 50;vector<vector<int> > G, parent;int root = 0, V;vector<int> depth;LowestCommonAncestor(int _V){V = _V;G.resize(V);parent.resize(MAX_LOG_V, vector<int>(V));depth.resize(V);}void add_edge(int u, int v){G[u].push_back(v);G[v].push_back(u);}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 build(){dfs(root, -1, 0);for(int k = 0; k + 1 < MAX_LOG_V; k++){for(int v = 0; v < V; v++){if(parent[k][v] < 0) parent[k + 1][v] = -1;else parent[k + 1][v] = parent[k][parent[k][v]];}}}int query(int u, int v){if(depth[u] > depth[v]) swap(u, v);for(int k = 0; k < MAX_LOG_V; k++){if((depth[v] - depth[u]) >> k & 1){v = parent[k][v];}}if(u == v) return u;for(int k = MAX_LOG_V - 1; k >= 0; k--){if(parent[k][u] != parent[k][v]){u = parent[k][u];v = parent[k][v];}}return parent[0][u];}};struct BIT{int N;vector<int> dat;BIT() {}BIT(int n) {N = n;dat.resize(N + 1);}// update k th element (0-index)void add(int k, int x){k++;while(k <= N){dat[k] += x;k += k&-k;}}// sum [0, k) (0-index)int sum(int k){int s = 0;while(k > 0){s += dat[k];k -= k&-k;}return s;}// sum [a, b) (0-index)int query(int a, int b){return sum(b) - sum(a);}};class Euler_Tour{public:vector<vector<int> > g;//begin[v],end[v]はそれぞれvがオイラーツアー上で最初と最後に現れるインデックス//[begin[v], end[v])がvを根とする部分木 (半開区間に注意)vector<int> euler_tour, begin, end, dist;Euler_Tour(int n) : /* g(n),*/ begin(n), end(n){};int k = 0, root = 0;void dfs(int curr, int par){begin[curr] = k;euler_tour.push_back(curr);k++;for(auto next : g[curr]){if(next == par) continue;dfs(next, curr);euler_tour.push_back(curr);k++;}end[curr] = k;}};struct edge{int v, w;};vector<edge> G[100010];map<P, int> cst;int sum[100010];int depth[100010];int dfs(int v, int p, int dep){depth[v] = dep;if(G[v].size() == 1) return 0;for(auto i : G[v]){if(i.v == p) continue;sum[v] += dfs(i.v, v, dep + 1) + i.w;}return sum[v];}signed main(){cin.tie(nullptr);ios::sync_with_stdio(false);int n;cin >> n;LowestCommonAncestor lca(n);Euler_Tour et(n);et.g.resize(n);rep(i, 0, n - 1){int u, v, w;cin >> u >> v >> w;G[u].push_back({v, w});G[v].push_back({u, w});lca.add_edge(u, v);et.g[u].push_back(v);et.g[v].push_back(u);cst[{u, v}] = w;cst[{v, u}] = w;}dfs(0, -1, 0);et.dfs(0, -1);BIT bt(2 * n);lca.build();rep(i, 0, 2 * n - 2){int u = et.euler_tour[i];int v = et.euler_tour[i + 1];if(depth[u] < depth[v]) bt.add(i, cst[{u, v}]);else bt.add(i, -cst[{u, v}]);}int q;cin >> q;while(q--){vector<int> p(3);cin >> p[0] >> p[1] >> p[2];int ans = INF;sort(p.begin(), p.end());do{int u1 = lca.query(p[0], p[1]);int u2 = lca.query(p[1], p[2]);int tmp = bt.query(et.begin[u1], et.begin[p[0]]) + bt.query(et.begin[u1], et.begin[p[1]]) + bt.query(et.begin[u2], et.begin[p[2]]) + abs(bt.query(et.begin[u1], et.begin[u2]));ans = min(ans, tmp);}while(next_permutation(p.begin(), p.end()));cout << ans << endl;}}