#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int NMAX = 5e5, KMAX = 20;
int par[NMAX + 5], sz[NMAX + 5], lift[NMAX + 5][KMAX + 5], d[NMAX + 5], h[NMAX + 5], root[NMAX + 5], rootCentroid, ans[NMAX + 5];
bool vis[NMAX + 5];
vector<pair<int, int>> adj[NMAX + 5];
void dfs(int u, int e) {
lift[u][0] = e;
for (int i = 1; i < KMAX; i++) lift[u][i] = lift[lift[u][i - 1]][i - 1];
for (auto&x : adj[u]) {
int v = x.first, c = x.second;
if (v == e) continue;
d[v] = d[u] + c, h[v] = h[u] + 1;
dfs(v, u);
}
}
bool set_bit(int mask, int k) { return mask & (1ll << k); }
int lca(int u, int v) {
if (h[u] > h[v]) swap(u, v);
int diff = h[v] - h[u];
for (int i = KMAX - 1; i >= 0; i--) {
if (!set_bit(diff, i)) continue;
v = lift[v][i];
}
if (u == v) return u;
for (int i = KMAX - 1; i >= 0; i--) {
if (lift[u][i] != lift[v][i]) {
u = lift[u][i], v = lift[v][i];
}
}
return lift[u][0];
}
int getDistance(int u, int v) {
int w = lca(u, v);
return d[u] + d[v] - 2*d[w];
}
void dfs2(int u, int e) {
sz[u] = 1;
for (auto&x : adj[u]) {
int v = x.first;
if (v == e || vis[v]) continue;
dfs2(v, u);
sz[u] += sz[v];
}
}
int findCentroid(int u, int e, int S) {
for (auto&x : adj[u]) {
int v = x.first;
if (v == e || vis[v] || sz[v] <= S/2) continue;
return findCentroid(v, u, S);
}
return u;
}
int buildCentroid(int u) {
dfs2(u, -1);
int curCentroid = findCentroid(u, -1, sz[u]);
vis[curCentroid] = true;
for (auto&x : adj[curCentroid]) {
int v = x.first;
if (vis[v]) continue;
int nextCentroid = buildCentroid(v);
root[nextCentroid] = curCentroid;
}
return curCentroid;
}
void Init(signed N, signed A[], signed B[], signed D[]) {
for (int i = 0; i < N - 1; i++) {
adj[A[i]].push_back({B[i], D[i]});
adj[B[i]].push_back({A[i], D[i]});
}
dfs(0, -1);
rootCentroid = buildCentroid(0);
root[rootCentroid] = -1;
}
long long Query(signed S, signed X[], signed T, signed Y[]) {
for (int i = 0; i < T; i++) {
for (int j = Y[i]; j != -1; j = root[j]) {
ans[j] = 1e18;
}
}
for (int i = 0; i < S; i++) {
for (int j = X[i]; j != -1; j = root[j]) {
ans[j] = 1e18;
}
}
for (int i = 0; i < T; i++) {
for (int j = Y[i]; j != -1; j = root[j]) {
ans[j] = min(ans[j], getDistance(Y[i], j));
}
}
int res = 1e18;
for (int i = 0; i < T; i++) {
for (int j = X[i]; j != -1; j = root[j]) {
res = min(res, getDistance(X[i], j) + ans[j]);
}
}
return res;
}
/*signed main() {
signed N, Q;
cin >> N >> Q;
signed A[N], B[N], D[N];
for (int i = 0; i < N - 1; i++) cin >> A[i] >> B[i] >> D[i];
Init(N, A, B, D);
for (int i = 0; i < Q; i++) {
int S, T;
cin >> S >> T;
signed X[S], Y[T];
for (int j = 0; j < S; j++) cin >> X[j];
for (int j = 0; j < T; j++) cin >> Y[j];
cout << Query(S, X, T, Y) << '\n';
}
return 0;
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
12628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
12628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
