#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 5e5 + 10;
int st[N], ed[N], h[N], vtx[N << 1], f[21][N << 1], num[N], a[N << 1];
long long d[N], nearest[3][N], res;
int cnt, timer;
bool mark1[N], mark2[N];
vector<pair<int, int> > adj[N];
vector<int> ke[N];
void dfs(int u) {
st[u] = ++timer;
vtx[++cnt] = u;
num[u] = cnt;
for(auto [v, w] : adj[u]) if (!st[v]) {
h[v] = h[u] + 1; d[v] = d[u] + w;
dfs(v);
vtx[++cnt] = u;
}
ed[u] = timer;
}
int lca(int u, int v) {
int l = num[u], r = num[v];
if (l > r) swap(l, r);
int k = log2(r - l + 1);
int x = f[k][l], y = f[k][r - (1 << k) + 1];
return h[x] < h[y] ? x : y;
}
void solve(int u) {
nearest[1][u] = nearest[2][u] = 1e18;
if (mark1[u]) nearest[1][u] = d[u];
if (mark2[u]) nearest[2][u] = d[u];
for(int v : ke[u]) {
solve(v);
for(int j = 1; j <= 2; j++) nearest[j][u] = min(nearest[j][u], nearest[j][v]);
}
res = min(res, nearest[1][u] + nearest[2][u] - 2 * d[u]);
}
void Init (int n, int a[], int b[], int d[]) {
for(int i = 0; i <= n - 2; i++) {
adj[a[i]].emplace_back(b[i], d[i]);
adj[b[i]].emplace_back(a[i], d[i]);
}
dfs(0);
for(int i = 1; i <= cnt; i++) f[0][i] = vtx[i];
for(int j = 1; j <= log2(cnt); j++) for(int i = 1; i + (1 << j) - 1 <= cnt; i++) {
int x = f[j - 1][i], y = f[j - 1][i + (1 << (j - 1))];
f[j][i] = h[x] < h[y] ? x : y;
}
}
long long Query(int s, int x[], int t, int y[]) {
res = 1e18;
int k = 0;
for(int i = 0; i < s; i++) a[++k] = x[i];
for(int i = 0; i < t; i++) a[++k] = y[i];
sort(a + 1, a + k + 1, [] (int &x, int &y) { return st[x] < st[y]; });
stack<int> S;
a[0] = a[k];
for(int i = 1; i <= k; i++) a[i + k] = lca(a[i], a[i - 1]);
k <<= 1;
sort(a + 1, a + k + 1, [] (int &x, int &y) { return st[x] < st[y]; });
S.push(a[1]);
for(int i = 2; i <= k; i++) if (a[i] != a[i - 1]) {
while (ed[S.top()] < st[a[i]]) S.pop();
ke[S.top()].push_back(a[i]);
S.push(a[i]);
}
solve(a[1]);
for(int i = 1; i <= k; i++) mark1[a[i]] = mark2[a[i]] = 0, ke[a[i]].clear();
return res;
}
//int main() {
// #define task ""
// cin.tie(0) -> sync_with_stdio(0);
// if (fopen ("task.inp", "r")) {
// freopen ("task.inp", "r", stdin);
// freopen ("task.out", "w", stdout);
// }
// if (fopen (task".inp", "r")) {
// freopen (task".inp", "r", stdin);
// freopen (task".out", "w", stdout);
// }
// int n, q; cin >> n >> q;
// for(int i = 1; i < n; i++) {
// int u, v, d; cin >> u >> v >> d;
// adj[u].emplace_back(v, d);
// adj[v].emplace_back(u, d);
// }
// dfs(0);
// for(int i = 1; i <= cnt; i++) f[0][i] = vtx[i];
// for(int j = 1; j <= log2(cnt); j++) for(int i = 1; i + (1 << j) - 1 <= cnt; i++) {
// int x = f[j - 1][i], y = f[j - 1][i + (1 << (j - 1))];
// f[j][i] = h[x] < h[y] ? x : y;
// }
// while (q--) {
// res = 1e18;
// int s, t; cin >> s >> t;
// for(int i = 1; i <= s; i++) cin >> a[i], mark1[a[i]] = 1;
// for(int i = s + 1; i <= s + t; i++) cin >> a[i], mark2[a[i]] = 2;
// int k = s + t;
// sort(a + 1, a + k + 1, [] (int &x, int &y) { return st[x] < st[y]; });
// stack<int> S;
// a[0] = a[k];
// for(int i = 1; i <= k; i++) a[i + k] = lca(a[i], a[i - 1]);
// k <<= 1;
// sort(a + 1, a + k + 1, [] (int &x, int &y) { return st[x] < st[y]; });
// S.push(a[1]);
// for(int i = 2; i <= k; i++) if (a[i] != a[i - 1]) {
// while (ed[S.top()] < st[a[i]]) S.pop();
// ke[S.top()].push_back(a[i]);
// S.push(a[i]);
// }
// solve(a[1]);
// cout << res << endl;
// for(int i = 1; i <= k; i++) mark1[a[i]] = mark2[a[i]] = 0, ke[a[i]].clear();
// }
//}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
24508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
24148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
24508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
