結果
問題 | 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; } } }