#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 1e6 + 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] = 1e16;
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] - 2LL * 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 = 1e16;
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
47692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
47512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
47692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
