#include<bits/stdc++.h>
#include"factories.h"
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<LL,LL> pii;
typedef pair<LL,pii> ppi;
typedef pair<pii,pii> ppp;
#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define mp make_pair
#define pb push_back
#define f first
#define s second
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {cout << "["; F0R(i, v.size()) {if (i) cout << ", "; cout << v[i];} return cout << "]";}
const LL INF = 1e17;
struct centroid{
LL mn = INF;
LL mn2 = INF;
LL mnch = -1;
};
struct parcen{
LL depth;
LL parent;
LL pphead;
};
//var
LL n, c, sub[500005], v[500005], dep[500005];
vector<pii> e[500005];
centroid cc[500005];
vector<parcen> pc[500005];
int N, A[500005], B[500005], C[500005], S, T, X[500005], Y[500005], Q;
void dfs_sub(LL g, LL p){
sub[g] = 1;
for(auto u : e[g]){
if(v[u.s] || u.s == p) continue;
dfs_sub(u.s, g);
sub[g] += sub[u.s];
}
}
LL cen(LL g, LL p, LL sz){
for(auto u : e[g]){
if(u.s == p || v[u.s]) continue;
if(sub[u.s] * 2 > sz) return cen(u.s, g, sz);
}
return g;
}
void dfs_dep(LL g, LL p, LL d, LL pp = 0){
dep[g] = d;
parcen tt;
if(p == c) pp = g;
tt.depth = d;
tt.parent = c;
tt.pphead = pp;
pc[g].pb(tt);
for(auto u : e[g]){
if(u.s == p || v[u.s]) continue;
dfs_dep(u.s, g, d + u.f, pp);
}
}
void make_tree(LL g, LL sz){
dfs_sub(g, 0);
c = cen(g, 0, sz);
dfs_sub(c, 0);
dfs_dep(c, 0, 0);
v[c] = 1;
for(auto u : e[c]){
if(v[u.s]) continue;
make_tree(u.s, sub[u.s]);
}
}
void Init(int N, int A[], int B[], int C[]){
n = N;
F0R(i, n-1){
e[A[i]+1].pb({C[i], B[i]+1});
e[B[i]+1].pb({C[i], A[i]+1});
}
make_tree(1, n);
}
LL Query(int S, int X[], int T, int Y[]){
F0R(i, S){
for(auto u : pc[X[i]+1]){
centroid& x = cc[u.parent];
if(x.mnch == u.pphead)
x.mn = min(x.mn, u.depth);
else{
if(u.depth < x.mn){
x.mn2 = x.mn;
x.mn = u.depth;
x.mnch = u.pphead;
}
else if(u.depth < x.mn2)
x.mn2 = u.depth;
}
}
}
LL ans = INF;
F0R(i, T){
for(auto u: pc[Y[i] + 1]){
centroid x = cc[u.parent];
if(u.pphead == x.mnch)
ans = min(ans, u.depth + x.mn2);
else ans = min(ans, u.depth + x.mn);
}
}
F0R(i, S){
for(auto u : pc[X[i] + 1]){
centroid& x = cc[u.parent];
x.mnch = -1;
x.mn = INF;
x.mn2 = INF;
}
}
return ans;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> Q;
F0R(i, N-1) cin >> A[i] >> B[i] >> C[i];
Init(N, A, B, C);
F0R(i, Q){
cin >> S >> T;
F0R(i, S) cin >> X[i];
F0R(i, T) cin >> Y[i];
cout << Query(S, X, T, Y) << '\n';
}
cout.flush();
return 0;
}
Compilation message
/tmp/ccmOEe0c.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccjpRPts.o:factories.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
