#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define maxn 500010
const int MOD = 1000000007;
struct lca_lift {
const int lg = 24;
int n;
vector<int> depth;
vector<long long> val;
vector<vector<pair<int, int>>> edges;
vector<vector<int>> lift;
void init(int sz) {
n = sz + 1;
depth = vector<int>(n);
val = vector<long long>(n);
edges = vector<vector<pair<int, int>>>(n, vector<pair<int, int>>());
lift = vector<vector<int> >(n, vector<int>(lg, -1));
}
void edge(int a, int b, int w) {
edges[a].push_back({b, w});
edges[b].push_back({a, w});
}
void init_lift(int v = 1) {
depth[v] = val[v] = 0;
dfs(v, -1);
}
void dfs(int v, int par) {
lift[v][0] = par;
for (int i = 1; i < lg; i++) {
if (lift[v][i - 1] == -1) lift[v][i] = -1;
else lift[v][i] = lift[lift[v][i - 1]][i - 1];
}
for (auto x: edges[v]) {
if (x.first != par) {
val[x.first] = x.second + val[v];
depth[x.first] = depth[v] + 1;
dfs(x.first, v);
}
}
}
int get(int v, int k) {
for (int i = lg - 1; i >= 0; i--) {
if (v == -1) return v;
if ((1 << i) <= k) {
v = lift[v][i];
k -= (1 << i);
}
}
return v;
}
int get_lca(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
int d = depth[a] - depth[b];
int v = get(a, d);
if (v == b) {
return v;
} else {
for (int i = lg - 1; i >= 0; i--) {
if (lift[v][i] != lift[b][i]) {
v = lift[v][i];
b = lift[b][i];
}
}
return lift[b][0];
}
}
long long get_dist(int a, int b) {
long long v = get_lca(a, b);
return val[a] + val[b] - 2 * val[v];
}
};
long long best[maxn];
int vis[maxn];
struct centroid {
vector<vector<int>> edges;
vector<bool> vis;
vector<int> par, sz;
int n;
void init(int s) {
n = s + 1;
edges = vector<vector<int>>(n, vector<int>());
vis = vector<bool>(n, 0);
par = sz = vector<int>(n);
}
void edge(int a, int b) {
edges[a].push_back(b);
edges[b].push_back(a);
}
int find_size(int u, int p = -1) {
if (vis[u])return 0;
sz[u] = 1;
for (auto x: edges[u]) {
if (x == p)continue;
sz[u] += find_size(x, u);
}
return sz[u];
}
int find_centroid(int u, int p, int n) {
for (auto x:edges[u]) {
if (x == p)continue;
if (!vis[x] and sz[x] > n / 2)return find_centroid(x, u, n);
}
return u;
}
void init_centroid(int u = 1, int p = -1) {
find_size(u);
int c = find_centroid(u, -1, sz[u]);
vis[c] = true;
par[c] = p;
for (auto x: edges[c]) {
if (!vis[x])init_centroid(x, c);
}
}
};
int v[maxn];
centroid c;
lca_lift lca;
void Init(int N, int A[], int B[], int D[]) {
c.init(N);
lca.init(N);
for (int i = 0; i < N - 1; i++) {
c.edge(A[i] + 1, B[i] + 1);
lca.edge(A[i] + 1, B[i] + 1, D[i]);
}
c.init_centroid();
lca.init_lift();
}
int No = 1;
void update(int node) {
int cur = node;
while (cur != -1) {
if (vis[cur] != No) {
vis[cur] = No;
best[cur] = lca.get_dist(cur, node);
} else best[cur] = min(best[cur], lca.get_dist(cur, node));
cur = c.par[cur];
}
}
long long query(int node) {
int cur = node;
long long ans = LLONG_MAX;
while (cur != -1) {
if (vis[cur] == No) ans = min(ans, lca.get_dist(cur, node) + best[cur]);
cur = c.par[cur];
}
return ans;
}
long long Query(int S, int X[], int T, int Y[]) {
long long ans = LLONG_MAX;
for (int i = 0; i < S; i++) update(X[i] + 1);
for (int i = 0; i < T; i++)ans = min(ans, query(Y[i] + 1));
No++;
return ans;
}
void solve() {
int n, q;
cin >> n >> q;
int 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;
int 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) << endl;
}
}
//int32_t main() {
// ios_base::sync_with_stdio(false);
// cin.tie(nullptr);
//
// int t = 1;
//// cin >> t;
//
// while (t--)
// solve();
// return 0;
//}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
768 KB |
Output is correct |
| 2 |
Correct |
1139 ms |
9852 KB |
Output is correct |
| 3 |
Correct |
2062 ms |
9976 KB |
Output is correct |
| 4 |
Correct |
1592 ms |
9848 KB |
Output is correct |
| 5 |
Correct |
2350 ms |
10232 KB |
Output is correct |
| 6 |
Correct |
435 ms |
9848 KB |
Output is correct |
| 7 |
Correct |
2033 ms |
10076 KB |
Output is correct |
| 8 |
Correct |
2092 ms |
10104 KB |
Output is correct |
| 9 |
Correct |
2321 ms |
10360 KB |
Output is correct |
| 10 |
Correct |
439 ms |
9976 KB |
Output is correct |
| 11 |
Correct |
1991 ms |
10056 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
640 KB |
Output is correct |
| 2 |
Correct |
3804 ms |
153936 KB |
Output is correct |
| 3 |
Execution timed out |
8055 ms |
155104 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
768 KB |
Output is correct |
| 2 |
Correct |
1139 ms |
9852 KB |
Output is correct |
| 3 |
Correct |
2062 ms |
9976 KB |
Output is correct |
| 4 |
Correct |
1592 ms |
9848 KB |
Output is correct |
| 5 |
Correct |
2350 ms |
10232 KB |
Output is correct |
| 6 |
Correct |
435 ms |
9848 KB |
Output is correct |
| 7 |
Correct |
2033 ms |
10076 KB |
Output is correct |
| 8 |
Correct |
2092 ms |
10104 KB |
Output is correct |
| 9 |
Correct |
2321 ms |
10360 KB |
Output is correct |
| 10 |
Correct |
439 ms |
9976 KB |
Output is correct |
| 11 |
Correct |
1991 ms |
10056 KB |
Output is correct |
| 12 |
Correct |
3 ms |
640 KB |
Output is correct |
| 13 |
Correct |
3804 ms |
153936 KB |
Output is correct |
| 14 |
Execution timed out |
8055 ms |
155104 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
