#ifndef mikevui
#include "task.h"
#endif // mikevui
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)
template<typename T> bool maximize(T &x, const T &y) {
if (x < y) {x = y; return 1;}
return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
if (x > y) {x = y; return 1;}
return 0;
}
const int maxn = 5e5+5, lg = 20;
const ll INF = 3e18;
int n;
vector<pair<int, ll>> a[maxn];
int tin[maxn], tout[maxn], timer = 0, par[maxn][lg+1];
ll dis[maxn];
//virtual tree
vector<pair<int, ll>> adj[maxn];
int c[maxn];
ll mi1[maxn], mi2[maxn], ans = LLONG_MAX;
bool cmp(int u, int v) {
return tin[u] < tin[v];
}
void dfspre(int u, int p) {
tin[u] = ++timer;
for (int j = 1; j <= lg; j++) {
par[u][j] = par[par[u][j-1]][j-1];
}
for (int i = 0; i < (int)a[u].size(); i++) {
int v = a[u][i].fi;
ll w = a[u][i].se;
if (v == p) continue;
dis[v] = dis[u]+w;
par[v][0] = u;
dfspre(v, u);
}
tout[u] = timer;
}
bool inside(int u, int v) {
return (tin[u] <= tin[v] && tout[v] <= tout[u]);
}
int lca(int u, int v) {
if (inside(u, v)) return v;
if (inside(v, u)) return u;
for (int j = lg; j >= 0; j--) {
while (par[u][j] > 0 && !inside(par[u][j], v)) {
u = par[u][j];
}
}
return par[u][0];
}
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];
a[u].pb({v, w});
a[v].pb({u, w});
}
dis[1] = 0;
dfspre(1, -1);
memset(mi1, 0x3f, sizeof(mi1));
memset(mi2, 0x3f, sizeof(mi2));
memset(c, 0, sizeof(c));
}
void dfsup(int u) {
if (c[u] == 1) {
mi1[u] = 0;
}
for (int i = 0; i < (int)adj[u].size(); i++) {
int v = adj[u][i].fi;
ll w = adj[u][i].se;
dfsup(v);
if (mi1[v] >= INF) continue;
ll val = mi1[v]+w;
if (val < mi1[u]) {
mi2[u] = mi1[u];
mi1[u] = val;
}
else if (val < mi2[u]) {
mi2[u] = val;
}
if (c[u] == 2){
minimize(ans, val);
}
}
}
void dfsdown(int u, ll down) {
if (c[u] == 2 && down < INF) {
minimize(ans, down);
}
// cout << u << ' ' << down << "\n";
for (int i = 0; i < (int)adj[u].size(); i++) {
int v = adj[u][i].fi;
ll w = adj[u][i].se;
ll val = min(down, (mi1[v] < INF && mi1[v]+w == mi1[u] ? mi2[u] : mi1[u]));
if (val < INF) val += w;
dfsdown(v, val);
}
}
long long Query(int S, int X[], int T, int Y[]){
ans = INF;
//build virtual tree
vector<int> nodes;
for (int i = 0; i < S; i++) {
int u = X[i]+1;
nodes.push_back(u);
c[u] = 1;
}
for (int i = 0; i < T; i++) {
int u = Y[i]+1;
nodes.push_back(u);
if (c[u] == 1) {
return 0LL;
}
c[u] = 2;
}
sort(nodes.begin(), nodes.end(), cmp);
int k = nodes.size();
for (int i = 1; i < k; i++) {
nodes.push_back(lca(nodes[i], nodes[i-1]));
}
sort(nodes.begin(), nodes.end(), cmp);
nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
k = nodes.size();
vector<int> st;
st.pb(nodes[0]); //root
for (int i = 1; i < k; i++) {
while (!inside(st.back(), nodes[i])) st.pop_back();
int u = st.back(), v = nodes[i];
adj[u].pb({v, dis[v]-dis[u]});
st.push_back(v);
// cout << u << ' ' << v << ' ' << dis[v]-dis[u] << "\n";
}
//solve, up and down
dfsup(nodes[0]);
// for (int i = 0; i < k; i++) {
// cout << nodes[i] << ' ' << mi1[nodes[i]] << ' ' << mi2[nodes[i]] << "\n";
// }
dfsdown(nodes[0], INF);
//reset
for (int i = 0; i < k; i++) {
int u = nodes[i];
adj[u].clear();
c[u] = 0;
mi1[u] = mi2[u] = INF;
}
return ans;
}
int N, Q, A[maxn], B[maxn], D[maxn], S, T, X[maxn], Y[maxn];
#ifdef mikevui
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
// #define name "task"
// if (fopen(name".inp", "r")) {
// freopen(name".inp", "r", stdin);
// freopen(name".out", "w", stdout);
// }
cin >> N >> Q;
for (int i = 0; i < N-1; i++) {
cin >> A[i] >> B[i] >> D[i];
}
Init(N, A, B, D);
while (Q--) {
cin >> S >> T;
for (int i = 0; i < S; i++) {
cin >> X[i];
}
for (int i = 0; i < T; i++) {
cin >> Y[i];
}
cout << Query(S, X, T, Y) << "\n";
}
}
#endif // mikevui
/*
7 1
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
2 2
0 6
3 4
7 3
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
2 2
0 6
3 4
3 2
0 1 3
4 6
1 1
2
5
*/
Compilation message
factories.cpp:2:14: fatal error: task.h: No such file or directory
2 | #include "task.h"
| ^~~~~~~~
compilation terminated.
