#include "factories.h"
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct CentroidTree{
int n;
vector<int> pa;
void cons(int n, vector<vector<int>> &adj){
pa.resize(n+1, -1);
vector<bool> ban(n+1, false);
vector<int> sub(n+1);
int tree_size;
auto rt = [&](auto rt, int u, int p) -> void{
sub[u] = 1;
for(int v : adj[u]){
if(v == p || ban[v]) continue;
rt(rt, v, u);
sub[u]+=sub[v];
}
};
auto find = [&](auto find, int u, int p) -> int{
for(int v : adj[u]){
if(v == p || ban[v]) continue;
if(sub[v]*2 > tree_size){
return find(find, v, u);
}
}
return u;
};
auto build = [&](auto build, int u, int p) -> void{
rt(rt, u, u);
tree_size = sub[u];
int c = find(find, u, u);
ban[c] = true;
pa[c] = p;
for(int v : adj[c]){
if(ban[v]) continue;
build(build, v, c);
}
};
build(build, 1, 0);
};
};
struct Tree{
int n, root;
vector<int> depth, head, sz, pa;
vector<int> f;
void cons(int n, int root, vector<vector<int>> &adj){
depth.resize(n+1, -1);
head.resize(n+1);
sz.resize(n+1, 0);
pa.resize(n+1, -1);
auto rootTree = [&](auto rootTree, int u, int p) -> void{
depth[u] = depth[p]+1;
pa[u] = p;
sz[u] = 1;
for(int v : adj[u]){
if(v == p) continue;
rootTree(rootTree, v, u);
sz[u] += sz[v];
}
};
rootTree(rootTree, root, 0);
auto decompose = [&](auto decompose, int u, int h) -> void{
head[u] = h;
int heavy = -1;
for(int v : adj[u]){
if(v == pa[u]) continue;
if(heavy == -1 || sz[heavy] < sz[v]) heavy = v;
}
if(heavy != -1) decompose(decompose, heavy, h);
for(int v : adj[u]){
if(v == pa[u] || v == heavy) continue;
decompose(decompose, v, v);
}
};
decompose(decompose, root, root);
f = [&]{
vector<array<int, 2>> first(n+1);
vector<array<int, 2>> second(n+1);
function<void(int, int)> dfs0 = [&](int u, int p) {
first[u] = second[u] = {0, -1};
for (int v : adj[u]) {
if (v == p) {
continue;
}
dfs0(v, u);
auto fetch = first[v];
fetch[0] += 1;
fetch[1] = v;
if (fetch > first[u]) {
swap(fetch, first[u]);
}
if (fetch > second[u]) {
swap(fetch, second[u]);
}
}
};
dfs0(1, 0);
function<void(int, int)> dfs = [&](int u, int p) {
for (int v : adj[u]) {
if (v == p) {
continue;
}
auto fetch = first[u][1] == v ? second[u] : first[u];
fetch[0] += 1;
fetch[1] = u;
if (fetch > first[v]) {
swap(fetch, first[v]);
}
if (fetch > second[v]) {
swap(fetch, second[v]);
}
dfs(v, u);
}
};
dfs(1, 0);
vector<int> f(n+1);
for (int u = 1; u <= n; u++) {
f[u] = first[u][0];
}
return f;
}();
};
int lca(int u, int v){
for(; head[u] != head[v]; v = pa[head[v]]){
if(depth[head[u]] > depth[head[v]]) swap(u, v);
}
if(depth[u] > depth[v]) swap(u, v);
return u;
}
int dist(int u, int v) {
return depth[u]+depth[v]-2*depth[lca(u, v)];
}
};
CentroidTree CT;
Tree TR;
vector<ll> depth, f;
void Init(int n, int A[], int B[], int D[]) {
vector<vector<int>> adj(n+1);
vector<vector<pair<int, int>>> adj2(n+1);
for(int i = 0; i < n-1; i++){
int u = A[i], v = B[i], w = D[i];
u++; v++;
adj[u].push_back(v);
adj[v].push_back(u);
adj2[u].push_back({v, w});
adj2[v].push_back({u, w});
}
depth.resize(n+1, 0);
f.resize(n+1, INF);
auto dfs = [&](auto dfs, int u, int p) -> void{
for(auto it : adj2[u]){
int v = it.first, w = it.second;
if(v == p) continue;
depth[v] = depth[u]+w;
dfs(dfs, v, u);
}
};
dfs(dfs, 1, 0);
CT.cons(n, adj);
TR.cons(n, 1, adj);
}
ll dist(int u, int v){
return depth[u]+depth[v]-depth[TR.lca(u, v)]*2;
}
long long Query(int S, int X[], int T, int Y[]) {
ll res = INF;
for(int i = 0; i < T; i++){
int v = Y[i];
v++;
int u = v;
while(u != 0){
f[u] = min(f[u], dist(u, v));
u = CT.pa[u];
}
}
for(int i = 0; i < S; i++){
int v = X[i];
v++;
int u = v;
while(u != 0){
res = min(res, f[u]+dist(u, v));
u = CT.pa[u];
}
}
for(int i = 0; i < T; i++){
int v = Y[i];
v++;
int u = v;
while(u != 0){
f[u] = INF;
u = CT.pa[u];
}
}
return res;
}
