// REPUTATION RATING = -100
//#include "factories.h"
#include <bits/stdc++.h>
//#define ll long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()
using namespace std;
typedef pair<ll,ll> pii;
typedef tuple<ll,ll,ll> tp;
const ll N = 5e5 + 5;
const ll oo = 1e16;
const ll mod = 1e9 + 7;
ll n, q, f[N][22], in[N], en[N], demin, a[N];
ll d[N], dp[N];
ll st[N << 1];
vector<pii> p[N];
void dfs(ll u,ll v){
in[u] = ++demin;
a[in[u]] = u;
// cout << u << " ";
if(u == 1) for(ll i = 0; i <= 20; i ++) f[u][i] = u;
else{
f[u][0] = v;
for(ll i = 1; i <= 20; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
}
for(auto jj : p[u]){
ll j = jj.fi;
ll w = jj.se;
if(j == v) continue;
d[j] = d[u] + w;
dfs(j, u);
}
en[u] = demin;
}
bool kt(ll u,ll v){
return in[u] <= in[v] && in[v] <= en[u];
}
ll lca(ll u,ll v){
if(kt(u, v)) return u;
else{
ll kq = u;
for(ll i = 20; i >= 0; i --){
if(kt(f[u][i], v)) kq = f[u][i];
else u = f[u][i];
}
return kq;
}
}
void update(ll i,ll x){
i += n - 1;
st[i] = x;
while(i > 1){
i /= 2;
if(d[st[i << 1]] < d[st[i << 1|1]]) st[i] = st[i << 1];
else st[i] = st[i << 1|1];
}
}
ll get(ll l,ll r){
r++;
ll ret = 0;
for(l += n - 1, r += n - 1; l < r; l /= 2, r /= 2){
if(l & 1){
if(d[st[l]] < d[ret]) ret = st[l];
l++;
}
if(r & 1){
--r;
if(d[st[r]] < d[ret]) ret = st[r];
}
}
return ret;
}
void Init(ll N, ll A[], ll B[], ll D[]){
n = N;
d[0] = oo;
for(ll i = 0; i < n - 1; i ++){
ll x = A[i] + 1, y = B[i] + 1, w = D[i];
// cerr << x << " " << y << " " << w << "\n";
p[x].pb({y, w});
p[y].pb({x, w});
}
dfs(1, 0);
// cout << "\n";
for(ll i = 1; i <= 2 * n; i ++) st[i] = 0;
}
long long Query(ll S, ll X[], ll T, ll Y[]){
vector<ll> vr;
for(ll i = 0; i < S; i ++) vr.pb(++X[i]);
for(ll i = 0; i < T; i ++) vr.pb(++Y[i]);
ll ans = (ll)1e18;
// ll kq = (ll)1e18;
// for(ll i = 0; i < S; i ++)
// for(ll j = 0; j < T; j ++)
// kq = min(kq, d[X[i]] + d[Y[j]] - 1LL * 2 * d[lca(X[i], Y[j])]);
// return kq;
// cerr << S << " " << T << "\n";
sort(vr.begin(), vr.end(), [] (ll x,ll y){return in[x] <= in[y];});
vector<ll> R;
// for(auto j : vr) cerr << j << " ";
// cerr << "\n";
R.pb(vr[0]);
p[vr[0]].clear();
for(ll i = 1; i < vr.size(); i ++){
ll u = lca(vr[i], vr[i - 1]);
R.pb(vr[i]);
R.pb(u);
// cerr << vr[i] << " " << vr[i - 1] << " " << u << "d\n";
p[vr[i]].clear();
p[u].clear();
}
sort(all(R), [] (ll x,ll y){return x < y;});
R.resize(unique(all(R)) - R.begin());
sort(all(R), [] (ll x,ll y){return in[x] <= in[y];});
// for(auto j : R) cerr << j << " ";
// cerr << "\n";
stack<ll> s;
s.push(R[0]);
dp[R[0]] = oo;
for(ll i = 1; i < R.size(); i ++){
dp[R[i]] = oo;
while(!s.empty() && !kt(s.top(), R[i])) s.pop();
ll w = d[R[i]] - d[s.top()];
// cerr << R[i] << " " << s.top() << " " << w << "g\n";
p[s.top()].pb({R[i], w});
p[R[i]].pb({s.top(), w});
// cerr << p[R[i]].back().se << "gg\n";
s.push(R[i]);
}
priority_queue<pii,vector<pii>,greater<pii>> pq;
for(ll i = 0; i < S; i ++) pq.push({dp[X[i]] = 0, X[i]});
while(!pq.empty()){
ll w = pq.top().fi;
ll u = pq.top().se;
pq.pop();
if(w > dp[u]) continue;
// cerr << u << " " << w << "f\n";
for(auto jj : p[u]){
ll j = jj.fi;
ll ts = jj.se;
// cerr << j << " " << ts << "f\n";
if(dp[j] > dp[u] + ts){
pq.push({dp[j] = dp[u] + ts, j});
// cerr << j << " " << dp[j] << " " << dp[u] << " " << ts << "g\n";
}
}
}
// cerr << "f\n";
for(ll i = 0; i < T; i ++) ans = min(ans, dp[Y[i]]);
return ans;
}
#define LOCAL
ll A[N], B[N], C[N], X[N], Y[N], S, T;
#ifdef LOCAL
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "v"
if(fopen(task ".inp","r")){
freopen(task ".inp","r",stdin);
freopen(task ".out","w",stdout);
}
cin >> n >> q;
for(ll i = 0; i < n - 1; i ++){
cin >> A[i] >> B[i] >> C[i];
}
Init(n, A, B, C);
while(q--){
cin >> S >> T;
for(ll i = 0; i < S; i ++) cin >> X[i];
for(ll i = 0; i < T; i ++) cin >> Y[i];
cout << Query(S, X, T, Y) << "\n";
}
}
#endif // LOCAL
Compilation message
factories.cpp: In function 'long long int Query(long long int, long long int*, long long int, long long int*)':
factories.cpp:125:21: 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]
125 | for(ll i = 1; i < vr.size(); i ++){
| ~~^~~~~~~~~~~
factories.cpp:141:21: 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]
141 | for(ll i = 1; i < R.size(); i ++){
| ~~^~~~~~~~~~
factories.cpp: In function 'int main()':
factories.cpp:189:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
189 | freopen(task ".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
factories.cpp:190:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
190 | freopen(task ".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccOYYZtd.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccB6Y20g.o:factories.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccOYYZtd.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
