#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 5e5 + 12;
typedef long long ll;
vector<pair<int, ll>> adj[mxN];
bool vis[mxN];
int sub[mxN];
//plasim se da ce biti sporo :/
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(2*sub[e] > n)
return centroid(e, s, n);
}
return s;
}
unordered_map<int, ll> dist[mxN];
void dfs(int s, int p, int c) {
ll vrednost = -1;
for(auto b : adj[s]) {
int e = b.first;
if(e == p) {
vrednost = b.second;
break;
}
}
if(vrednost == -1) {
dist[c][s] = 0;
} else {
dist[c][s] = dist[c][p] + vrednost;
}
for(auto b : adj[s]) {
int e = b.first;
if(e == p || vis[e])
continue;
dfs(e, s, c);
}
}
int iznad[mxN];
void build(int s, int p = -1) {
int n = dfsSize(s);
int c = centroid(s, -1, n);
int vel;
if(n <= 1) {
vel = 1;
} else {
vel = 31 - __builtin_clz(n);
}
dist[c].reserve(1<<vel);
dist[c].max_load_factor(0.25);
dfs(c, -1, c);
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) {
//vector<pair<int, ll>> temp;
//for(auto z : dist[i]) {
//temp.push_back(z);
//}
//cout << i << ":";
//for(auto z : temp)
//cout << " {" << z.first << ", " << z.second << "}";
//cout << endl;
//}
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];
int iteriraj = trenutni;
while(iteriraj != -1) {
mini[iteriraj] = min(mini[iteriraj], dist[iteriraj][trenutni]);
iteriraj = iznad[iteriraj];
}
}
for(int i = 0; i < T; ++i) {
int trenutni = Y[i];
int iteriraj = trenutni;
while(iteriraj != -1) {
if(mini[iteriraj] != LLONG_MAX) {
ans = min(ans, mini[iteriraj] + dist[iteriraj][trenutni]);
}
iteriraj = iznad[iteriraj];
}
}
for(int i = 0; i < S; ++i) {
int iteriraj = X[i];
while(iteriraj != -1) {
mini[iteriraj] = LLONG_MAX;
iteriraj = iznad[iteriraj];
}
}
return ans;
}
