#include "factories.h"
#include "factories.h"
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>
using namespace std;
const int MAXN = 5e5+5;
const int mod7 = 1e9+7;
const long long inf = 1e15;
const int lg = 20;
int t = 1;
vector<vector<pii>> graf(MAXN);
vector<vector<int>> centoidgraf(MAXN);
vector<long long> rez;
int subtreesize[MAXN];
int dist[MAXN];
int tin[MAXN];
int tout[MAXN];
int parents[MAXN];
int up[MAXN][lg];
bool wasCentoid[MAXN];
int root;
int n,q;
void dfs(int nod, int p, int d)
{
dist[nod] = d;
tin[nod] = t++;
up[nod][0] = p;
for(auto x: graf[nod])if(x.fi != p)dfs(x.fi, nod, d+x.sc);
tout[nod] = t++;
}
void fillUp()
{
for(int i=1; i<lg; i++)
{
for(int j=0; j<n; j++)
{
up[j][i] = up[up[j][i-1]][i-1];
}
}
}
int lca(int u, int v)
{
if(u==v)return u;
if(tin[u] < tin[v] && tout[u] > tout[v])return u;
if(tin[u] > tin[v] && tout[u] < tout[v])return v;
for(int i=lg-1; i>=0; i--)
{
int guess = up[v][i];
if(tin[u] < tin[guess] && tout[u] > tout[guess])v = guess;
}
return up[v][0];
}
int dfs2(int nod, int p)
{
subtreesize[nod] ++;
for(auto x: graf[nod])
{
if(x.fi == p || wasCentoid[x.fi])continue;
subtreesize[nod] += dfs2(x.fi, nod);
}
return subtreesize[nod];
}
int findCentroid(int nod, int p, int treesize)
{
for(auto x: graf[nod])
{
if(x.fi==p || wasCentoid[x.fi])continue;
if(subtreesize[x.fi] * 2 > treesize)return findCentroid(x.fi, nod, treesize);
}
return nod;
}
void solve(int nod, int p, bool foundroot)
{
int treesize = dfs2(nod, nod);
int centroid = findCentroid(nod, nod, treesize);
wasCentoid[centroid] = 1;
parents[centroid] = p;
if(!foundroot)
{
root = centroid;
parents[centroid] = centroid;
}
else centoidgraf[p].pb(centroid);
for(auto x:graf[centroid])
{
if(wasCentoid[x.fi])continue;
solve(x.fi, centroid, true);
}
}
int findDist(int u, int v)
{
return dist[u] + dist[v] - 2*dist[lca(u,v)];
}
void update(int nod)
{
int trnod = nod;
while(trnod != parents[trnod])
{
rez[trnod] = min(rez[trnod],findDist(nod, trnod));
trnod = parents[trnod];
}
rez[trnod] = min(rez[trnod], findDist(nod, trnod));
}
int query(int nod)
{
int trnod = nod;
long long trrez= inf;
while(trnod != parents[trnod])
{
trrez = min(trrez, rez[trnod] + findDist(nod, trnod));
trnod = parents[trnod];
}
trrez = min(trrez, rez[trnod] + findDist(nod, trnod));
return trrez;
}
/*
signed main()
{
ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
int tt=1;
//cin >> tt;
while(tt--)
{
cin >> n >> q;
rez = vector<long long>(n, inf);
for(int i=0; i<n-1; i++)
{
int a,b,w;cin >> a >> b >> w;
graf[a].pb({b,w});
graf[b].pb({a,w});
}
dfs(0,0,0);
fillUp();
solve(0,0,false);
//for(int i=0; i<n; i++)cout << parents[i] << " ";cout << endl;
while(q--)
{
int a,b;cin >> a >> b;
vector<int> factory1(a);
for(int i=0; i<a; i++)
{
cin >> factory1[i];
update(factory1[i]);
}
vector<int> factory2(b);
int finalrez = inf;
for(int i=0; i<b; i++)
{
cin >> factory2[i];
finalrez = min(finalrez, query(factory2[i]));
}
///reset cenmtorid tree
for(int i=0; i<n; i++)
{
int nod = i;
while(rez[nod] !=inf)
{
rez[nod] = inf;
nod = parents[nod];
}
}
cout << finalrez << endl;
}
}
}
*/
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i=0; i<n-1; i++)
{
graf[A[i]].pb({B[i],D[i]});
graf[B[i]].pb({A[i],D[i]});
}
dfs(0,0,0);
fillUp();
solve(0,0,false);
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i=0; i<S; i++)update(X[i]);
int finalrez = inf;
for(int i=0; i<T; i++)finalrez = min(finalrez, query(Y[i]));
for(int i=0; i<n; i++)
{
int nod = i;
while(rez[nod] !=inf)
{
rez[nod] = inf;
nod = parents[nod];
}
}
return finalrez;
}
Compilation message
/usr/bin/ld: /tmp/ccivEs97.o: in function `main':
grader.cpp:(.text.startup+0x37d): undefined reference to `Init(int, int*, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x412): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status
