//============================================================================
// Name : joi14p1.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Scan and Debug
void scan(){}
template<typename F, typename... R> void scan(F &f,R&... r){cin>>f;scan(r...);}
int di_; string dnms_, co_ = ",";
void debug_(){cout<<endl;}
template<typename F, typename... R> void debug_(F f, R... r){while(dnms_[di_] != ',')cout<<dnms_[di_++];di_++;cout<<": "<<f<<",";debug_(r...);}
#define debug(...) dnms_=#__VA_ARGS__+co_,di_=0,debug_(__VA_ARGS__)
const int MAX = 500001;
struct ed {
int v, w;
};
vector<ed> matrix[MAX];
const ll INF = 0x3f3f3f3f3f3f3f3f;
int N,
sz[MAX], par[MAX], lv[MAX];
bool blocked[MAX];
ll bestFor[MAX];
vector<int> back;
vector<ll> dis[MAX];
int gsz(int cur, int par) {
sz[cur] = 1;
for (ed adj : matrix[cur])
if ((adj.v ^ par) && !blocked[adj.v])
sz[cur] += gsz(adj.v, cur);
return sz[cur];
}
int gcentroid(int cur, int par, int half) {
for (ed adj : matrix[cur])
if ((adj.v ^ par) && !blocked[adj.v] && sz[adj.v] > half)
return gcentroid(adj.v, cur, half);
return cur;
}
void dfs(int cur, int par=-1, ll __dis=0) {
dis[cur].push_back(__dis);
for (ed adj : matrix[cur])
if ((adj.v ^ par) && !blocked[adj.v])
dfs(adj.v, cur, __dis + adj.w);
}
int decomp(int cur=0, int __par=-1, int __lv=0) {
gsz(cur, __par);
if (sz[cur] == 1) {// If size is one, centroid is self
lv[cur] = __lv;
return cur;
}
int centroid = gcentroid(cur, __par, sz[cur] >> 1);
lv[centroid] = __lv;
blocked[centroid] = true;
dfs(centroid);
for (ed adj : matrix[centroid])
if (!blocked[adj.v])
par[decomp(adj.v, centroid, __lv + 1)] = centroid;
return centroid;
}
// Grader Functions
void Init(int N_, int A[], int B[], int D[]) {
N = N_;
for (int i = 0; i < N - 1; i++) {
matrix[A[i]].push_back({B[i], D[i]});
matrix[B[i]].push_back({A[i], D[i]});
}
// Init Centroid Tree
par[decomp()] = -1;
memset(bestFor, 0x3f, sizeof bestFor);
}
long long Query(int S, int X[], int T, int Y[]) {
ll best = INF;
for (int i = 0; i < T; i++) {
for (int cur = Y[i], clv = lv[cur]; cur != -1; cur = par[cur], clv--) {
bestFor[cur] = min(bestFor[cur], dis[Y[i]][clv]), assert(cur != par[cur]);
back.push_back(cur);
}
}
for (int i = 0; i < S; i++)
for (int cur = X[i], clv = lv[cur]; cur != -1; cur = par[cur], clv--)
best = min(best, dis[X[i]][clv] + bestFor[cur]), assert(cur != par[cur]);
for (int x : back)
bestFor[x] = INF;
back.clear();
return best;
}
