#include <bits/stdc++.h>
#include "factories.h"
#define int long long
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
using namespace std;
const int O = 5e5 + 5;
const int N = 2e5 + 5;
const int mod = 1e9 + 7; //998244353;
const int inf = 1e18;
int pr[] = {167772161, 469762049, 754974721, 1045430273, 1051721729, 1053818881};
int n, q, p[O], h[O], val[O], child[O], f[21][O], W[21][O];
vector <pair <int, int>> g[O];
pair <int, int> dp[2][O];
bool del[O];
void init(int u, int par = 0){
for (auto &to : g[u]){
int v = to.first;
int w = to.second;
if (v != par){
h[v] = h[u] + 1;
init(v, u);
f[0][v] = u;
W[0][v] = w;
}
}
}
int Lca(int u, int v){
int res = 0;
if (h[u] < h[v]) swap(u, v);
for (int i = 20; i >= 0; -- i){
if (h[u] - (1 << i) >= h[v]){
res += W[i][u];
u = f[i][u];
}
}
if (u == v) return res;
for (int i = 20; i >= 0; -- i){
if (f[i][u] != f[i][v]){
res += W[i][u];
res += W[i][v];
u = f[i][u];
v = f[i][v];
}
}
res += W[0][u];
res += W[0][v];
return res;
}
void dfs_init(int u, int par = -1){
child[u] = 1;
for (auto &to : g[u]){
int v = to.first;
int w = to.second;
if (v != par && !del[v]){
dfs_init(v, u);
child[u] += child[v];
}
}
}
int centroid(int u, int par, int Nchild){
for (auto &to : g[u]){
int v = to.first;
if (v != par && !del[v] && child[v] * 2 > Nchild) return centroid(v, u, Nchild);
}
return u;
}
int dfs_centroid(int u){
dfs_init(u);
int root = centroid(u, -1, child[u]);
del[root] = 1;
for (auto &v : g[root]){
if (!del[v.first]){
int nxt = dfs_centroid(v.first);
int x = Lca(root, nxt);
p[nxt] = root;
val[nxt] = x;
//cout << root << " " << nxt << " " << x << endl;
}
}
return root;
}
void Init(int N, int A[], int B[], int D[]){
n = N;
for (int i = 0; i < n - 1; ++ i){
int u, v, w; //cin >> u >> v >> w;
u = A[i];
v = B[i];
w = D[i];
//u = i; v = i + 1; w = 0;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
memset(f, -1, sizeof(f));
memset(p, -1, sizeof(p));
init(0);
for (int i = 1; i <= 20; ++ i){
for (int j = 0; j < n; ++ j){
if (f[i - 1][j] != -1){
f[i][j] = f[i - 1][f[i - 1][j]];
W[i][j] = W[i - 1][j] + W[i - 1][f[i - 1][j]];
}
}
}
//cout << "deba" << endl;
dfs_centroid(0);
//cout << "deba" << endl;
for (int i = 0; i < n; ++ i) dp[0][i] = dp[1][i] = {inf, -1};
/*for (int i = 1; i <= q; ++ i){
int S, T;
cin >> S >> T;
int X[1000], Y[1000];
for (int j = 0; j < S; ++ j){
int x; cin >> x;
X[j] = x;
}
for (int j = 0; j < T; ++ j){
int x; cin >> x;
Y[j] = x;
}
//cout << "debug " << i << endl;
cout << Query(S, X, T, Y) << "\n";
//cout << "debug " << i << endl << endl;
}*/
}
long long Query(int S, int X[], int T, int Y[]){
int res = inf;
for (int i = 0; i < S; ++ i){
int u = X[i];
pair <int, int> cur = {0, -1};
while (u != -1){
if (dp[0][u].first > cur.first){
pair <int, int> x = dp[0][u];
dp[0][u] = cur;
if (cur.second != x.second) dp[1][u] = x;
}
else{
if (dp[1][u].first > cur.first && cur.second != dp[0][u].second){
dp[1][u] = cur;
}
}
cur.first = dp[0][u].first + val[u];
cur.second = u;
u = p[u];
}
}
/*for (int i = 0; i < n; ++ i){
cout << i << " : " << dp[0][i].first << " " << dp[0][i].second << endl;
cout << i << " : " << dp[1][i].first << " " << dp[1][i].second << endl;
}*/
for (int i = 0; i < T; ++ i){
int u = Y[i];
int cur = 0;
res = min(res, dp[0][u].first);
while (u != -1){
int par = p[u];
cur += val[u];
if (par != -1){
res = min(res, cur + (dp[0][par].second == u ? dp[1][par].first : dp[0][par].first));
}
u = par;
}
}
for (int i = 0; i < S; ++ i){
int u = X[i];
while (u != -1){
dp[0][u] = dp[1][u] = {inf, -1};
u = p[u];
}
}
return res;
}
/*main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
}*/
/***
***/
Compilation message
factories.cpp: In function 'void dfs_init(long long int, long long int)':
factories.cpp:65:13: warning: unused variable 'w' [-Wunused-variable]
65 | int w = to.second;
| ^
/usr/bin/ld: /tmp/cchVTXFk.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
