#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <queue>
#include <stack>
#include <cassert>
#include <cstring>
#include <climits>
#include <functional>
#include <cstdlib>
#include <complex>
#include <array>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <random>
#define fileIO(name) if(fopen(name".in", "r")) {freopen(name".in", "r", stdin); freopen(name".out", "w", stdout);}
using namespace std;
const int MAXN = 4e5 + 111;
using ll = long long;
const int P = 31;
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
using ld = long double;
const ld EPS = 1e-5;
using pii = pair<int, int>;
typedef complex<ll> Point;
int n;
vector<pair<int,int>> adj[MAXN];
int sz[MAXN];
bool vis[MAXN];
ll best[MAXN];
ll dis[MAXN][20];
int lev[MAXN];
int par[MAXN];
int find_size(int v,int p)
{
if (vis[v])
return 0;
sz[v] = 1;
for (auto u : adj[v])
{
if (u.first == p)
continue;
sz[v] += find_size(u.first, v);
}
return sz[v];
}
int find_centroid(int v, int p,int n)
{
for (auto u : adj[v])
{
if (u.first == p || vis[u.first])
continue;
if (sz[u.first] > n / 2)
return find_centroid(u.first, v, n);
}
return v;
}
void dfs(int v,int S, int p)
{
for (auto u : adj[v])
{
if (u.first == p || vis[u.first])
continue;
dis[u.first][lev[u.first] - lev[S]] =
dis[v][lev[v] - lev[S]] + u.second;
dfs(u.first, S, v);
}
}
void decomp1(int v,int p)
{
find_size(v, v);
int c = find_centroid(v, v, sz[v]);
vis[c] = true;
par[c] = p;
if (p != -1)
lev[c] = lev[p] + 1;
for (auto u : adj[c])
{
if (!vis[u.first])
decomp1(u.first, c);
}
}
void decomp2(int v)
{
find_size(v, v);
int c = find_centroid(v, v, sz[v]);
vis[c] = true;
dfs(c, -1, c);
for (auto u : adj[c])
{
if (!vis[u.first])
decomp2(u.first);
}
}
void Init(int _n, int a[], int b[], int d[])
{
fill(par, par + MAXN, -1);
fill(best, best + MAXN, 1e18);
for (int i = 0; i < n-1; i++)
{
adj[a[i] + 1].push_back({ b[i] + 1,d[i] });
adj[b[i] + 1].push_back({ a[i] + 1,d[i] });
}
decomp1(1, -1);
fill(vis, vis + MAXN, 0);
decomp2(1);
}
ll Query(int s, vector<int> x, int t, vector<int> y)
{
for (int i = 0; i < s; i++)
{
int a = x[i];
int j = 0;
while (a != -1)
{
best[a] = min(best[a], dis[x[i]][j]);
j++;
a = par[a];
}
}
ll ans = 1e18;
for (int i = 0; i < t; i++)
{
int b = y[i];
int j = 0;
while (b != -1)
{
ans = min(ans, dis[y[i]][j] + best[b]);
b = par[b];
j++;
}
}
for (int i = 0; i < s; i++)
{
int a = x[i];
while (a != -1)
{
best[a] = 1e18;
a = par[a];
}
}
return ans;
}
Compilation message
/usr/bin/ld: /tmp/ccr01nRE.o: in function `main':
grader.cpp:(.text.startup+0x412): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status
