/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/JOI14_factories
*/
#include <iostream> //cin , cout
#include <fstream> //fin, fout
#include <stdio.h> // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack> // stacks
#include <queue> // queues
#include <map>
#include <string>
#include <set>
#include "factories.h"
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi; /// adjlist without weight
typedef vector<pii> vii; /// adjlist with weight
typedef vector<pair<int,pii>> vpip; /// edge with weight
typedef long long ll;
#define mp make_pair
#define fst first
#define snd second
#define pb push_back
#define sz(x) (int)(x).size()
#define trav(u, adj_v) for (auto& u: adj_v)
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
#define MAXV 500007
#define MAXE 100007
bool debug;
int N, Q;
vi adjlist[MAXV];
map<int, ll> adjmap[MAXV];
int qct;
struct NODE {
vector<int> cenlist; /// list of centroid ID for each node
vector<ll> cenDist; /// corresponding distance of node to each centroid
int subtreeSize;
};
NODE nodes[MAXV];
/// centroid property
struct CENTR {
int from; /// the original point for centroid is from (child of upper level centroid)
ll mdist; /// shortest distance from red to this centriod
bool visited;
int cleared;
};
CENTR cents[MAXV];
int dfs_size(int cur, int parent) {
nodes[cur].subtreeSize = 1;
for (int v : adjlist[cur])
if (v != parent && !cents[v].visited)
nodes[cur].subtreeSize += dfs_size(v, cur);
return nodes[cur].subtreeSize;
}
int find_cent(int cur, int parent, int cenSize) {
for (int v : adjlist[cur])
if (v != parent && !cents[v].visited)
if (nodes[v].subtreeSize * 2 > cenSize) // not using >=, keep centroid close to top
return find_cent(v, cur, cenSize);
return cur;
}
static void dfs_depth(int cur, int parent, int cid, ll depth) {
nodes[cur].cenlist.pb(cid);
nodes[cur].cenDist.pb(depth);
for (int v : adjlist[cur])
if (v != parent && !cents[v].visited)
dfs_depth(v, cur, cid, depth + adjmap[cur][v]);
}
void buildCentriod(int top, int parent) {
/// find centriod
dfs_size(top, parent);
int c = find_cent(top, parent, nodes[top].subtreeSize);
cents[c].from = top; cents[c].mdist = INF;
cents[c].visited = true; cents[c].cleared = -1;
/// assign tree behavior relative to this centroid
dfs_depth(c, 0, c, 0LL);
/// dfs, NlgN complexity
for (int v : adjlist[c])
if (!cents[v].visited) buildCentriod(v, c);
}
void Init(int _N, int A[], int B[], int D[]) {
N = _N;
for(int i=0; i<N-1; i++) {
int u = A[i]+1, v = B[i]+1; ll w = D[i];
adjlist[u].pb(v); adjlist[v].pb(u);
adjmap[u][v] = w; adjmap[v][u] = w;
}
buildCentriod(1, 0);
qct=0;
}
long long Query(int S, int X[], int T, int Y[]) {
qct++;
for(int i=0; i<S; i++) {
int a = X[i] + 1;
for(int j = 0; j < sz(nodes[a].cenlist); j++) {
int c = nodes[a].cenlist[j];
ll w = nodes[a].cenDist[j];
if(cents[c].cleared != qct) {
cents[c].mdist = w;
cents[c].cleared = qct;
} else {
cents[c].mdist = min(cents[c].mdist, w);
}
}
}
ll ret = INF;
for(int i=0; i<T; i++) {
int a = Y[i] + 1;
for(int j = 0; j < sz(nodes[a].cenlist); j++) {
int c = nodes[a].cenlist[j];
if(cents[c].cleared == qct) {
ll w = nodes[a].cenDist[j] + cents[c].mdist;
ret = min(ret, w);
}
}
}
return ret;
}
