//Dost SEFEROĞLU
//Lazy Persistent Dynamic 3D Segment Tree (feat. Selo)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e14;
const int N = 5e5+50;
int timer = 1;
vector<pii> edges[N];
int up[N][20],d[N],tin[N],tout[N],c[N],red[N],blue[N];
void dfs(int node,int p,int dep = 0) {
tin[node] = timer++;
d[node] = dep;
up[node][0] = p;
for (auto it : edges[node]) {
if (it.ff == p) continue;
dfs(it.ff,node,dep+it.ss);
}
tout[node] = timer-1;
}
bool anc(int a,int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a,int b) {
if (anc(a,b)) return a;
if (anc(b,a)) return b;
for (int i=19;i>=0;i--) {
if (!anc(up[a][i],b)) a = up[a][i];
}
return up[a][0];
}
vi edg[N];
int solver(int node) {
red[node] = blue[node] = inf;
if (c[node] == 1) red[node] = d[node];
if (c[node] == 2) blue[node] = d[node];
int ans = inf;
for (auto it : edg[node]) {
ans = min(ans,solver(it));
red[node] = min(red[node],red[it]);
blue[node] = min(blue[node],blue[it]);
}
//cout << node sp red[node] sp blue[node] sp d[node]<< endl;
ans = min(ans,red[node]+blue[node]-2*d[node]);
return ans;
}
void solve() {
int n,q;
cin >> n >> q;
for (int i=1;i<=n-1;i++) {
int a,b,c;
cin >> a >> b >> c;
edges[a].push_back({b,c});
edges[b].push_back({a,c});
}
dfs(0,0);
for (int i=1;i<20;i++) {
for (int j=0;j<n;j++) up[j][i] = up[up[j][i-1]][i-1];
}
while (q--) {
int s,t;
cin >> s >> t;
vector<int> nodes;
vi x(s),y(t);
for (int i=0;i<s;i++) {
cin >> x[i];
c[x[i]] = 1;
nodes.push_back(x[i]);
}
for (int i=0;i<t;i++) {
cin >> y[i];
c[y[i]] = 2;
nodes.push_back(y[i]);
}
sort(all(nodes),[&](int n1,int n2) {
return tin[n1] < tin[n2];
});
for (int i=0;i<s+t;i++) {
nodes.push_back(lca(nodes[i],nodes[(i+1)%nodes.size()]));
}
sort(all(nodes),[&](int n1,int n2) {
return tin[n1] < tin[n2];
});
nodes.erase(unique(all(nodes)),nodes.end());
stack<int> st;
st.push(nodes[0]);
for (int i=1;i<nodes.size();i++) {
while (!anc(st.top(),nodes[i])) {
st.pop();
}
edg[st.top()].push_back(nodes[i]);
st.push(nodes[i]);
}
int ans = solver(nodes[0]);
cout << ans << endl;
for (auto it : nodes) edg[it].clear(),c[it] = 0;
}
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Dodi
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
Compilation message
factories.cpp: In function 'void solve()':
factories.cpp:98:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (int i=1;i<nodes.size();i++) {
| ~^~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccROqfX2.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccRstSh4.o:factories.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccROqfX2.o: in function `main':
grader.cpp:(.text.startup+0x37d): undefined reference to `Init(int, int*, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x412): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status
