結果
| 問題 |
No.1212 Second Path
|
| コンテスト | |
| ユーザー |
 SSRS
|
| 提出日時 | 2020-08-30 16:57:01 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,664 bytes |
| コンパイル時間 | 6,022 ms |
| コンパイル使用メモリ | 230,744 KB |
| 最終ジャッジ日時 | 2025-01-14 00:20:18 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 16 TLE * 29 |
ソースコード
#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{
lowest_common_ancestor G;
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();
G = lowest_common_ancestor(p, c);
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 = G.query(v, w);
return BIT.query(left[u], left[v] + 1) + BIT.query(left[u] + 1, left[w] + 1);
}
};
template <typename T>
struct weighted_tree_distance{
vector<int> d;
vector<T> s;
vector<vector<int>> next;
weighted_tree_distance(vector<vector<pair<T, int>>> &E){
int N = E.size();
d = vector<int>(N, 0);
s = vector<T>(N, 0);
next = vector<vector<int>>(LOG, vector<int>(N, -1));
queue<int> Q;
Q.push(0);
while (!Q.empty()){
int v = Q.front();
Q.pop();
for (auto e : E[v]){
T c = e.first;
int w = e.second;
if (w != next[0][v]){
next[0][w] = v;
d[w] = d[v] + 1;
s[w] = s[v] + c;
Q.push(w);
}
}
}
for (int i = 1; i < LOG; i++){
for (int j = 0; j < N; j++){
if (next[i - 1][j] != -1){
next[i][j] = next[i - 1][next[i - 1][j]];
}
}
}
}
int lca(int u, int v){
if (d[u] < d[v]){
swap(u, v);
}
for (int i = 0; i < LOG; i++){
if ((d[u] - d[v]) >> i & 1){
u = next[i][u];
}
}
if (u == v){
return u;
} else {
for (int i = LOG - 1; i >= 0; i--){
if (next[i][u] != next[i][v]){
u = next[i][u];
v = next[i][v];
}
}
return next[0][u];
}
}
int dist1(int u, int v){
return d[u] + d[v] - 2 * d[lca(u, v)];
}
T dist2(int u, int v){
return s[u] + s[v] - 2 * s[lca(u, v)];
}
};
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> a(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);
a[w] = d;
q.push(w);
}
}
}
int Q;
cin >> Q;
vector<int> x(Q), y(Q);
for (int i = 0; i < Q; i++){
cin >> x[i] >> y[i];
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]);
int b = T2.query(x[id], y[id]);
int l = T1.G.query(x[id], y[id]);
if (used[l]){
b--;
}
if (a > b * 2){
tv[id] = i + 1;
} else {
fv[id] = i + 1;
}
}
}
}
weighted_tree_distance<long long> T(E);
for (int i = 0; i < Q; i++){
if (tv[i] == N){
cout << -1 << endl;
} else {
cout << T.dist2(x[i], y[i]) + get<0>(edges[tv[i] - 1]) * 2 << endl;
}
}
}