結果

問題 No.1212 Second Path
ユーザー SSRS
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0