#include "factories.h"
#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
vector<pair<int,int>> adj[500000];
int query_num, root, P[500000], W[500000], num[500000], cnt[500000];
long long V[500000], dist[500000][19];
bool chk[500000];
void reset(int c)
{
W[c]=0;
for(auto[n,w]: adj[c]) if(!chk[n] && W[n]) reset(n);
}
int dfs(int c)
{
W[c]=1; V[c]=-1;
for(auto[n,w]: adj[c]) if(!chk[n] && W[n]==0) W[c]+=dfs(n);
return W[c];
}
int dfs2(int c, int v)
{
for(auto[n,w]: adj[c]) if(W[n]<W[c] && 2*W[n]>v) return dfs2(n,v);
return c;
}
void dfs3(int c)
{
dist[c][cnt[c]++]=V[c];
for(auto[n,w]: adj[c]) if(!chk[n] && V[n]==-1) {
V[n]=V[c]+w;
dfs3(n);
}
}
int get_centroid(int c)
{
reset(c);
chk[c=dfs2(c,dfs(c))]=true;
dist[c][cnt[c]++]=V[c]=0;
for(auto[n,w]: adj[c]) if(!chk[n]) {
V[n]=w; dfs3(n);
P[get_centroid(n)]=c;
}
return c;
}
void Init(int N, vector<int> A, vector<int> B, vector<int> D)
{
for(int i=0;i<N-1;i++) {
adj[A[i]].emplace_back(B[i],D[i]);
adj[B[i]].emplace_back(A[i],D[i]);
}
root=get_centroid(0);
}
long long Query(int S, vector<int> X, int T, vector<int> Y)
{
long long ret=0x7fffffffffffffffLL;
int v; ++query_num;
for(int i=0;i<S;i++) {
v=cnt[X[i]];
for(int j=X[i];j!=root;j=P[j]) {
if(num[j]==query_num) V[j]=min(V[j],dist[X[i]][--v]);
else {
num[j]=query_num;
V[j]=dist[X[i]][--v];
}
}
if(num[root]==query_num) V[root]=min(V[root],dist[X[i]][--v]);
else {
num[root]=query_num;
V[root]=dist[X[i]][--v];
}
}
for(int i=0;i<T;i++) {
v=cnt[Y[i]];
for(int j=Y[i];j!=root;j=P[j]) {
v--;
if(num[j]!=query_num) continue;
ret=min(ret,V[j]+dist[Y[i]][v]);
}
ret=min(ret,V[root]+dist[Y[i]][--v]);
}
return ret;
}
Compilation message
/tmp/ccrx8NPW.o: In function `main':
grader.cpp:(.text.startup+0x317): undefined reference to `Init(int, int*, int*, int*)'
grader.cpp:(.text.startup+0x397): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status
