結果
問題 | No.898 tri-βutree |
ユーザー |
|
提出日時 | 2019-09-16 21:32:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 548 ms / 4,000 ms |
コード長 | 2,431 bytes |
コンパイル時間 | 2,082 ms |
コンパイル使用メモリ | 185,028 KB |
実行使用メモリ | 95,124 KB |
最終ジャッジ日時 | 2024-11-08 21:38:25 |
合計ジャッジ時間 | 12,982 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std;using i64 = long long;#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)#define all(x) x.begin(),x.end()#define let auto conststruct eulartour_subtree {vector<vector<pair<i64, i64>>> G;vector<i64> tour;vector<i64> L, R;vector<i64> depth;vector<i64> weight;eulartour_subtree(i64 n): G(n), L(n), R(n), depth(n), weight(n) {}void add_edge(i64 u, i64 v, i64 w) {G[u].push_back({v, w});G[v].push_back({u, w});}void dfs(i64 v, i64 f, i64 d, i64 w) {tour.push_back(v);L[v] = tour.size() - 1;depth[v] = d;weight[v] = w;for(auto to: G[v]) {if(to.first == f) continue;dfs(to.first, v, d + 1, w + to.second);tour.push_back(v);}R[v] = tour.size() - 1;}i64 start_tour(i64 r) {dfs(r, -1, 0, 0);return tour.size();}};#include <bits/stdc++.h>using namespace std;using i64 = long long;struct sparse_table {using Band = pair<i64, i64>;Band ope(const Band& a, const Band b) { return min(a, b); }i64 N;vector<Band> A;vector<i64> log_t;vector<vector<Band>> table;sparse_table(vector<Band> arr) : N(arr.size()), A(arr), log_t(arr.size() + 1) {for(int i = 2;i < N + 1;i++) {log_t[i] = log_t[i >> 1] + 1;}table.resize(N, vector<Band>(log_t[N] + 1));for(int i = 0;i < N;i++) {table[i][0] = arr[i];}for(int k = 1;(1 << k) <= N;k++) {for(int i = 0;i + (1 << k) <= N;i++) {table[i][k] = ope(table[i][k - 1], table[i + (1 << (k - 1))][k - 1]);}}}/* [s, t] */Band query(i64 s, i64 t) {i64 k = log_t[t - s + 1];return ope(table[s][k], table[t - (1 << k) + 1][k]);}};int main() {i64 N;cin >> N;eulartour_subtree eul(N);for(int i = 0;i < N - 1;i++) {i64 a, b, c;cin >> a >> b >> c;eul.add_edge(a, b, c);}i64 sz = eul.start_tour(0);vector<pair<i64, i64>> arr(sz);for(i64 i = 0;i < sz;i++) {arr[i] = { eul.depth[eul.tour[i]], eul.tour[i] };}sparse_table spa(arr);auto dist = [&](i64 a, i64 b) -> i64 {i64 c = spa.query(min(eul.L[a], eul.L[b]), max(eul.R[a], eul.R[b])).second;return eul.weight[a] + eul.weight[b] - 2 * eul.weight[c];};i64 Q;cin >> Q;for(i64 q = 0; q < Q; q++) {i64 x, y, z;cin >> x >> y >> z;cout << (dist(x, y) + dist(y, z) + dist(x, z)) / 2 << endl;}}