#include <bits/stdc++.h>
#ifndef saarang
#include "factories.h"
#endif
using namespace std;
std::mt19937 rng(15);
const int mxn = 500 * 1000 + 3, lgn = 20;
int up[mxn][lgn], d[mxn], par[mxn], sz[mxn], n;
long long dt[mxn], ans[mxn];
vector<array<int, 2>> g[mxn];
bool cent[mxn];
void dfs(int v, int p) {
up[v][0] = (p < 0 ? v : p);
for(auto &[u, w] : g[v]) if(u != p) {
d[u] = d[v] + 1;
dt[u] = dt[v] + w;
dfs(u, v);
}
for(int i = 1; i < lgn; i++)
up[v][i] = up[up[v][i - 1]][i - 1];
}
int kth(int v, int di) {
for(int i = 0; i < lgn; i++)
if(di >> i & 1)
v = up[v][i];
return v;
}
int lca(int a, int b) {
if(d[a] > d[b])
swap(a, b);
b = kth(b, d[b] - d[a]);
if(a == b) return a;
for(int i = lgn - 1; i >= 0; i--)
if(up[a][i] != up[b][i])
a = up[a][i], b = up[b][i];
return up[a][0];
}
long long dist(int a, int b) { return dt[a] + dt[b] - 2 * dt[lca(a, b)]; }
int dfssz(int v, int p) {
sz[v] = 1;
for(auto &[u, w] : g[v]) if(u != p && !cent[u])
sz[v] += dfssz(u, v);
return sz[v];
}
int fcent(int v, int p) {
for(auto &[u, w] : g[v]) if(u != p && !cent[u]) {
if(sz[u] > sz[v] / 2)
return fcent(u, v);
}
return v;
}
void decompose(int v, int p) {
dfssz(v, -1);
int centroid = fcent(v, -1);
cent[centroid] = true;
par[centroid] = p;
for(auto &[u, w] : g[centroid])
if(u != p && !cent[u])
decompose(u, centroid);
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i = 0; i < n - 1; i++) {
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
dfs(0, -1);
decompose(0, -1);
memset(ans, 0x7f, sizeof ans);
}
void upd(int v) {
for(int p = v; p != -1; p = par[p])
ans[p] = min(ans[p], dist(p, v));
}
void fix(int v) {
for(int p = v; p != -1; p = par[p])
ans[p] = ans[n];
}
long long query(int v) {
long long res = ans[n];
for(int p = v; p != -1; p = par[p])
res = min(res, ans[p] + dist(p, v));
return res;
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i = 0; i < T; i++)
upd(Y[i]);
long long answer = ans[n];
for(int i = 0; i < S; i++)
answer = min(answer, query(X[i]));
for(int i = 0; i < T; i++)
fix(Y[i]);
return answer;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
16620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
16236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
16620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
