#include <bits/stdc++.h>
const int maxn = 5e5 + 5;
const int LG = 19;
const long long INF = 1e17;
int n, q, timeDfs;
int sparse[1000005][LG + 5], par[maxn + 5];
int lg[maxn + 5], sz[maxn + 5], h[maxn + 5], tin[maxn + 5];
long long depth[maxn + 5], d[maxn + 5];
bool del[maxn + 5];
std::vector<int> nd;
std::vector<std::pair<int, int>> g[maxn + 5];
void init() {
for (int i = 2; i <= maxn; ++i)
lg[i] = lg[i / 2] + 1;
}
int combine(int u, int v) {
return h[u] < h[v] ? u : v;
}
void dfs(int u, int p) {
sparse[++timeDfs][0] = u;
tin[u] = timeDfs;
for (std::pair<int, int> tmp : g[u]) {
int v = tmp.first;
int w = tmp.second;
if (v == p) continue;
depth[v] = depth[u] + w;
h[v] = h[u] + 1;
dfs(v, u);
sparse[++timeDfs][0] = u;
}
}
int find_centroid(int u, int p, int m) {
for (std::pair<int, int> tmp : g[u]) {
int v = tmp.first;
if (del[v] || v == p) continue;
if (sz[v] > m / 2) return find_centroid(v, u, m);
}
return u;
}
void reset_sz(int u, int p) {
sz[u] = 1;
for (std::pair<int, int> tmp : g[u]) {
int v = tmp.first;
if (del[v] || v == p) continue;
reset_sz(v, u);
sz[u] += sz[v];
}
}
long long dist(int u, int v) {
if (tin[u] > tin[v]) std::swap(u, v);
int base = lg[tin[v] - tin[u] + 1];
int lca = combine(sparse[tin[u]][base], sparse[tin[v] - (1 << base) + 1][base]);
return depth[u] + depth[v] - 2 * depth[lca];
}
int CD(int u) {
reset_sz(u, 0);
int cen = find_centroid(u, 0, sz[u]);
del[cen] = true;
for (std::pair<int, int> tmp : g[cen]) {
int v = tmp.first;
if (del[v]) continue;
par[CD(v)] = cen;
}
return cen;
}
void update(int u) {
int anc = u;
while (anc) {
d[anc] = std::min(d[anc], dist(u, anc));
anc = par[anc];
}
}
long long query(int u) {
int anc = u;
long long ans = INF;
while (anc) {
ans = std::min(ans, dist(u, anc) + d[anc]);
anc = par[anc];
}
return ans;
}
void init_d(int u) {
int anc = u;
while (anc) {
d[anc] = INF;
anc = par[anc];
}
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for (int i = 0; i <= n - 2; ++i) {
int u = A[i];
int v = B[i];
int w = D[i];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs(1, 0);
for (int j = 1; j <= LG; ++j) {
for (int i = 1; i <= timeDfs; ++i) {
sparse[i][j] = combine(sparse[i][j - 1], sparse[i + (1 << (j - 1))][j - 1]);
}
}
CD(1);
init();
for (int i = 1; i <= n; ++i) d[i] = INF;
}
long long Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; ++i) {
int u = X[i];
nd.push_back(u);
update(u);
}
long long ans = INF;
for (int i = 0; i < T; ++i) {
int u = Y[i];
ans = std::min(ans, query(u));
}
for (int u : nd)
init_d(u);
nd.clear();
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
40528 KB |
Output is correct |
| 2 |
Incorrect |
320 ms |
44948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
40528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
40528 KB |
Output is correct |
| 2 |
Incorrect |
320 ms |
44948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
