結果
問題 | No.1212 Second Path |
ユーザー |
![]() |
提出日時 | 2020-08-30 17:02:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,116 ms / 3,000 ms |
コード長 | 4,236 bytes |
コンパイル時間 | 3,160 ms |
コンパイル使用メモリ | 229,212 KB |
最終ジャッジ日時 | 2025-01-14 00:24:08 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
#include <bits/stdc++.h>using namespace std;const int INF = 1000000000;const int LOG = 18;struct lowest_common_ancestor{vector<int> d;vector<vector<int>> p;lowest_common_ancestor(){}lowest_common_ancestor(vector<int> &P, vector<vector<int>> &C){int N = P.size();d = vector<int>(N, 0);queue<int> Q;Q.push(0);while (!Q.empty()){int v = Q.front();Q.pop();for (int w : C[v]){d[w] = d[v] + 1;Q.push(w);}}p = vector<vector<int>>(LOG, vector<int>(N, -1));for (int i = 0; i < N; i++){p[0][i] = P[i];}for (int i = 1; i < LOG; i++){for (int j = 0; j < N; j++){if (p[i - 1][j] != -1){p[i][j] = p[i - 1][p[i - 1][j]];}}}}int query(int u, int v){if (d[u] > d[v]){swap(u, v);}for (int k = 0; k < LOG; k++){if ((d[v] - d[u]) >> k & 1){v = p[k][v];}}if (u == v){return u;}for (int k = LOG - 1; k >= 0; k--){if (p[k][u] != p[k][v]){u = p[k][u];v = p[k][v];}}return p[0][u];}};template <typename T>struct binary_indexed_tree{int N;vector<T> BIT;binary_indexed_tree(){}binary_indexed_tree(int n){N = 1;while (N < n){N *= 2;}BIT = vector<T>(N + 1, 0);}void add(int i, T x){i++;while (i <= N){BIT[i] += x;i += i & -i;}}T sum(int i){T ans = 0;while (i > 0){ans += BIT[i];i -= i & -i;}return ans;}T query(int L, int R){return sum(R) - sum(L);}};template <typename T>struct euler_tour{vector<T> A;vector<int> left;vector<int> right;binary_indexed_tree<T> BIT;void dfs(vector<vector<int>> &c, int v){left[v] = A.size();A.push_back(0);for (int w : c[v]){dfs(c, w);}right[v] = A.size();A.push_back(0);}euler_tour(vector<int> &p, vector<vector<int>> &c){int N = p.size();left = vector<int>(N);right = vector<int>(N);dfs(c, 0);BIT = binary_indexed_tree<int>(N * 2);}void add(int v){BIT.add(left[v], 1);BIT.add(right[v], -1);}T query(int v, int w, int u){return BIT.query(left[u], left[v] + 1) + BIT.query(left[u] + 1, left[w] + 1);}};int main(){int N;cin >> N;vector<vector<pair<long long, int>>> E(N);vector<tuple<int, int, int>> edges;for (int i = 0; i < N - 1; i++){int u, v, w;cin >> u >> v >> w;u--;v--;E[u].push_back(make_pair(w, v));E[v].push_back(make_pair(w, u));edges.push_back(make_tuple(w, u, v));}vector<int> p(N, -1);vector<vector<int>> c(N);vector<long long> s(N, 0);queue<int> q;q.push(0);while (!q.empty()){int v = q.front();q.pop();for (auto e : E[v]){int d = e.first;int w = e.second;if (w != p[v]){p[w] = v;c[v].push_back(w);s[w] = s[v] + d;q.push(w);}}}lowest_common_ancestor LCA(p, c);int Q;cin >> Q;vector<int> x(Q), y(Q), l(Q);for (int i = 0; i < Q; i++){cin >> x[i] >> y[i];x[i]--;y[i]--;l[i] = LCA.query(x[i], y[i]);}sort(edges.begin(), edges.end());vector<int> tv(Q, N);vector<int> fv(Q, 0);while (1){bool upd = false;vector<vector<int>> check(N - 1);for (int i = 0; i < Q; i++){if (tv[i] - fv[i] > 1){upd = true;int mid = (tv[i] + fv[i]) / 2;check[mid - 1].push_back(i);}}if (!upd){break;}euler_tour<int> T1(p, c), T2(p, c);vector<bool> used(N, false);for (int i = 0; i < N - 1; i++){int u = get<1>(edges[i]);int v = get<2>(edges[i]);T1.add(u);T1.add(v);if (u == p[v]){T2.add(v);used[v] = true;} else {T2.add(u);used[u] = true;}for (int id : check[i]){int a = T1.query(x[id], y[id], l[id]);int b = T2.query(x[id], y[id], l[id]);if (used[l[id]]){b--;}if (a > b * 2){tv[id] = i + 1;} else {fv[id] = i + 1;}}}}for (int i = 0; i < Q; i++){if (tv[i] == N){cout << -1 << endl;} else {cout << s[x[i]] + s[y[i]] - s[l[i]] * 2 + get<0>(edges[tv[i] - 1]) * 2 << endl;}}}