#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 600012;
typedef long long ll;
vector<pair<int, ll>> adj[mxN];
bool vis[mxN];
int sub[mxN];
int dfsSize(int s, int p = -1) {
sub[s] = 1;
for(auto b : adj[s]) {
int e = b.first;
if(e == p || vis[e])
continue;
dfsSize(e, s);
sub[s] += sub[e];
}
return sub[s];
}
int centroid(int s, int p, int n) {
for(auto b : adj[s]) {
int e = b.first;
if(e == p || vis[e])
continue;
if(sub[e] > n/2)
return centroid(e, s, n);
}
return s;
}
vector<ll> dist[mxN];
void dfs(int s, int p = -1) {
ll vrednost = 0;
for(auto b : adj[s]) {
int e = b.first;
if(vis[e] || e == p) {
vrednost = b.second;
break;
}
}
if(p == -1) {
dist[s].push_back(0);
} else {
dist[s].push_back(vrednost + dist[p].back());
}
for(auto b : adj[s]) {
int e = b.first;
if(e == p || vis[e])
continue;
dfs(e, s);
}
}
int iznad[mxN];
void build(int s, int p = -1) {
int n = dfsSize(s);
int c = centroid(s, -1, n);
dfs(c, -1);
iznad[c] = p;
vis[c] = true;
for(auto b : adj[c]) {
int e = b.first;
if(vis[e])
continue;
build(e, c);
}
}
ll mini[mxN];
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0; i < N-1; ++i) {
int u = A[i], v = B[i];
ll w = D[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
build(0);
for(int i = 0; i < N; ++i) reverse(dist[i].begin(), dist[i].end());
for(int i = 0; i < N; ++i)
mini[i] = LLONG_MAX;
}
long long Query(int S, int X[], int T, int Y[]) {
//drzi za prve, za druge samo proveri
ll ans = LLONG_MAX;
for(int i = 0; i < S; ++i) {
int trenutni = X[i];
for(int j = trenutni, cnt = 0; j != -1; j = iznad[j], ++cnt) {
mini[j] = min(mini[j], dist[trenutni][cnt]);
}
}
for(int i = 0; i < T; ++i) {
int trenutni = Y[i];
for(int j = trenutni, cnt = 0; j != -1; j = iznad[j], ++cnt) {
if(mini[j] == LLONG_MAX) {
continue;
}
ans = min(ans, mini[j] + dist[trenutni][cnt]);
}
}
for(int i = 0; i < S; ++i) {
int trenutni = X[i];
for(int j = trenutni, cnt = 0; j != -1; j = iznad[j], ++cnt) {
mini[j] = LLONG_MAX;
}
}
return ans;
}
