#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
#define ll long long
#define endl "\n"
const int MOD = 998244353;
const int maxN = 500001;
const int maxEuler = 3000000;
const int maxlog = 20;
int sparse[maxEuler][23];
int euler[maxEuler];
int lb[maxEuler];
pair<int, int> t[maxN];
ll dists[maxN];
int depths[maxN];
vector<pair<int, ll>> adj[maxN];
bool done[maxN];
int subtree_size[maxN];
int parents[maxN];
ll ans[maxN];
int centr;
int root;
int cnt;
void DFS_lca(int x, int p){
t[x].first = cnt;
euler[cnt] = x; cnt++;
for(auto pr : adj[x]){
int node = pr.first;
if(node != p){
depths[node] = depths[x] + 1;
dists[node] = dists[x] + pr.second;
DFS_lca(node, x);
t[x].second = cnt;
euler[cnt] = x; cnt++;
}
}
if(t[x].first + 1 == cnt){
t[x].second = cnt;
euler[cnt] = x; cnt++;
}
}
void build_lca(int n){
depths[0] = 0;
dists[0] = 0;
cnt = 0;
DFS_lca(0, -1);
for(int i = 0; i < 23; i++){
for(int j = 0; j < cnt; j++){
if(i > 0){
if(depths[sparse[j][i - 1]] < depths[sparse[max(0, j - (1<<(i - 1)))][i - 1]]){
sparse[j][i] = sparse[j][i - 1];
}else sparse[j][i] = sparse[max(0, j - (1<<(i - 1)))][i - 1];
}
else sparse[j][i] = euler[j];
}
}
ll pw = 1;
int curr = 0;
for(int i = 1; i < maxEuler; i++){
if(i > pw){
pw *= 2; curr++;
}
lb[i] = curr;
}
}
int lca(int a, int b){
if(a == b) return a;
int l = min(t[a].first, t[b].first); int r = max(t[a].second, t[b].second);
int dst = r - l + 1;
if(depths[sparse[r][lb[dst]]] < depths[sparse[r - (1 << lb[dst])][lb[dst]]]) return sparse[r][lb[dst]];
else return sparse[r - (1 << lb[dst])][lb[dst]];
}
ll dist(int a, int b){
int anc = lca(a, b);
return dists[a] + dists[b] - 2 * dists[anc];
}
int find_size(int x, int par){
subtree_size[x] = 1;
for(auto pr : adj[x]){
int node = pr.first;
if(node == par || done[node] == 1) continue;
subtree_size[x] += find_size(node, x);
}
return subtree_size[x];
}
void find_centroid(int x, int par, int siz){
bool good = 1;
for(auto pr : adj[x]){
int node = pr.first;
if(node == par || done[node] == 1) continue;
if(subtree_size[node] > siz / 2){
find_centroid(node, x, siz);
good = 0;
}
}
if(good) centr = x;
}
void build(int n){
queue<pair<int, int>> q;
q.push({0, -1});
while(!q.empty()){
int x = q.front().first; int par = q.front().second; q.pop();
int siz = find_size(x, -1);
centr = -1;
find_centroid(x, -1, siz);
if(par == -1) root = centr;
parents[centr] = par;
done[centr] = 1;
for(auto pr : adj[centr]){
int node = pr.first;
if(!done[node]) q.push({node, centr});
}
}
}
void add(int x){
int next = x;
while(next != -1){
ll d = dist(next, x);
ans[next] = min(ans[next], d);
next = parents[next];
}
}
void rmv(int x){
int next = x;
while(next != -1){
ans[next] = 1e18;
next = parents[next];
}
}
ll query(int x){
int next = x;
ll rep = 1e18;
while(next != -1){
ll d = dist(next, x);
rep = min(rep, ans[next] + d);
next = parents[next];
}
return rep;
}
void Init(int N, int A[], int B[], int 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]});
}
build_lca(N);
build(N);
for(int i = 0; i < N; i++) ans[i] = 1e18;
}
ll Query(int S, int X[], int T, int Y[]){
for(int i = 0; i < S; i++) add(X[i]);
ll retrn = 1e18;
for(int i = 0; i < T; i++) retrn = min(retrn, query(Y[i]));
for(int i = 0; i < S; i++) rmv(X[i]);
return retrn;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
24360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
24104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
24360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
