#include <bits/stdc++.h>
#include <factories.h>
using namespace std;
#define ll long long
const int ar = 5e5 + 5;
int n, q, N, A[ar], B[ar], D[ar], X[ar];
int sz[ar], parent[ar];
multiset<ll> se[ar];
vector<int> adj[ar];
bool deleted[ar];
unordered_map<int, ll> dis[ar];
int vt[ar];
void dfs(int u, int par) {
++N;
sz[u] = 1;
for(auto x : adj[u]) if(x != par && !deleted[x]) {
dfs(x, u);
sz[u] += sz[x];
}
}
int find_centroid(int u, int par) {
for(auto x : adj[u]) if(x != par && !deleted[x] && sz[x] > N / 2) return find_centroid(x, u);
return u;
}
void build_distance(int u, int par, int c, ll d) {
dis[c][u] = d;
for(auto x : adj[u]) if(x != par && !deleted[x]) build_distance(x, u, c, d + dis[u][x]);
}
void build_tree(int u, int par) {
N = 0;
dfs(u, par);
int centroid = find_centroid(u, par);
parent[centroid] = par;
deleted[centroid] = 1;
build_distance(centroid, par, centroid, 0);
for(int x : adj[centroid]) if(x != parent[centroid] && !deleted[x]) build_tree(x, centroid);
}
void add(int u) {
for(int par = u; par; par = parent[par]) se[par].insert(dis[par][u]);
}
void del(int u) {
for(int par = u; par; par = parent[par]) se[par].erase(se[par].find(dis[par][u]));
}
ll get(int u) {
ll Min = 1e18;
for(int par = u; par; par = parent[par]) {
if(se[par].size()) Min = min(Min, dis[par][u] + *se[par].begin());
}
return Min;
}
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0; i < N - 1; ++i) {
A[i]++; B[i]++;
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
dis[A[i]][B[i]] = dis[B[i]][A[i]] = D[i];
}
build_tree(1, 0);
}
ll Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++)
add(X[i] + 1);
ll ans = 1e15;
for (int i = 0; i < T; i++)
ans = min(ans, get(Y[i] + 1));
for (int i = 0; i < S; i++)
(X[i] + 1);
return ans;
}
// int main() {
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// cin >> n >> q;
// for(int i = 0; i < n - 1; ++i) {
// int x, y, w; cin >> x >> y >> w;
// x++; y++;
// adj[x].push_back(y);
// adj[y].push_back(x);
// dis[x][y] = dis[y][x] = w;
// }
// build_tree(1, 0);
// while(q--) {
// int a, b; cin >> a >> b;
// for(int i = 1; i <= a; ++i) {
// cin >> vt[i];
// vt[i]++;
// add(vt[i]);
// }
// ll ans = 1e18;
// for(int i = 1; i <= b; ++i) {
// int u; cin >> u;
// u++;
// ans = min(ans, get(u));
// }
// for(int i = 1; i <= a; ++i) del(vt[i]);
// cout << ans << '\n';
// }
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
93008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
87384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
93008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
