#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
vector<pair<int,long long>> adj[200001];
int hi[200001];
int P[200001][18];
long long sum[200001][18];
void dfs(int i,int pr,long long len){
hi[i] = hi[pr]+1;
P[i][0]= pr;
sum[i][0] =len;
for(int j = 1;j<18;j++){
P[i][j] = P[P[i][j-1]][j-1];
sum[i][j]= sum[i][j-1]+sum[P[i][j-1]][j-1];
}
for(auto j:adj[i]){
if(j.first!=pr){
dfs(j.first,i,j.second);
}
}
}long long lca(int x,int y){
long long su = 0;
if(hi[x]<hi[y]) swap(x,y);
for(int k=17;k>=0;k--)
{
if(hi[x]-(1<<k) >= hi[y]){
su+=sum[x][k];
x=P[x][k];
}
}
if(x==y) return su;
for(int k=17;k>=0;k--)
{
if(P[x][k] != P[y][k]){
su+=sum[x][k]+sum[y][k];
x=P[x][k],y=P[y][k];
}
}
return su+sum[x][0]+sum[y][0];
}
int sz[200001];
int vis[200001];
int par[200001];
long long best[200001];
int vi[200001];
int va = 1;
void upd(int i){
long long s = i;
while(s!=-1){
if(vi[s]!=va){
vi[s] =va;
best[s] = 1e18;
}
best[s] = min(best[s],lca(i,s));
s= par[s];
}
}
long long ans(int i){
long long s = i , re = 1e18;
while(s!=-1){
if(vi[s]!=va){
vi[s] =va;
best[s] = 1e18;
}
re = min(re,best[s]+lca(i,s));
s= par[s];
}
return re;
}
int find_size(int v, int p = -1) {
if(vis[v]) return 0;
sz[v] = 1;
for(auto x: adj[v]) {
if (x.first != p) {
sz[v] += find_size(x.first, v);
}
}
return sz[v];
}
int find_centroid(int v, int p, int n) {
for (auto x: adj[v]) {
if (x.first != p) {
if (!vis[x.first] && sz[x.first] > n / 2) {
return find_centroid(x.first, v, n);
}
}
}
return v;
}
void centroid(int v = 0, int p = -1) {
find_size(v);
int c = find_centroid(v,-1,sz[v]);
vis[c] = true;
par[c] = p;
for(auto x:adj[c]) {
if (!vis[x.first]) {
centroid(x.first, c);
}
}
}
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]});
}
centroid();
dfs(0,0,0);
}
long long Query(int S, int X[], int T,int Y[]) {
for(int i = 0;i<S;i++){
upd(X[i]);
}
long long Res = 1e18;
for(int i = 0;i<T;i++){
Res = min(Res,ans(Y[i]));
}
va++;
return Res;
}
Compilation message
/usr/bin/ld: /tmp/cc7ckyVK.o: in function `main':
grader.cpp:(.text.startup+0x37d): undefined reference to `Init(int, int*, int*, int*)'
collect2: error: ld returned 1 exit status
