| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1279193 | hiepsimauhong | Factories (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(I, L, R) for(int I(L) ; I <= (int)R ; ++I)
#define FOD(I, R, L) for(int I(R) ; I >= (int)L ; --I)
#define FOA(I, A) for(auto &I : A)
#define print(A,L,R) FOR(OK, L, R){if(A[OK]<=-oo / 10||A[OK]>=oo)cout<<"- ";else cout<<A[OK]<<' ';}cout<<'\n';
#define prints(A) FOA(OK, A){cout<<OK<<' ';}cout << '\n';
#define printz(A,L,R) FOR(OK, 0, L){FOR(KO, 0, R){if(A[OK][KO]>-oo&&A[OK][KO]<oo)cout<<A[OK][KO]<<' ';else cout << "- ";} cout << '\n';}cout << '\n';
#define fs first
#define sd second
#define ii pair<int,int>
#define iii pair<int, ii>
#define all(A) A.begin(), A.end()
#define quickly cin.tie(0) -> ios_base::sync_with_stdio(0);
const int N = 5e5 + 5;
const int mod = 1e9 + 7;
const int oo = 1e18;
int n, q;
vector<ii> g[N];
struct LCA{
int up[N][21], high[N], h[N];
void build(int u, int par){
FOA(e, g[u]){
int v = e.fs, w = e.sd;
if(v == par){
continue;
}
h[v] = h[u] + 1;
high[v] = high[u] + w;
up[v][0] = u;
FOR(i, 1, 20){
up[v][i] = up[up[v][i - 1]][i - 1];
}
build(v, u);
}
}
int get(int u, int v){
if(h[v] < h[u]) swap(u, v);
int c = h[v] - h[u];
FOR(i, 0, 20){
if(c >> i & 1){
v = up[v][i];
}
}
if(u == v) return u;
FOD(i, 20, 0){
if(up[v][i] == up[u][i]){
continue;
}
v = up[v][i];
u = up[u][i];
}
return up[v][0];
}
int path(int u, int v){
return high[u] + high[v] - 2 * high[get(u, v)];
}
} lca;
namespace Centroid{
int sz[N], near[N], parent[N];
bool cen[N];
vector<int> ing[N];
void DFS(int u, int par){
sz[u] = 1;
FOA(e, g[u]){
int v = e.fs;
if(v == par || cen[v]){
continue;
}
DFS(v, u);
sz[u] += sz[v];
}
}
int find_centroid(int u, int par, int mx){
FOA(e, g[u]){
int v = e.fs;
if(v == par || cen[v]){
continue;
}
if(mx / 2 < sz[v]){
return find_centroid(v, u, mx);
}
}
return u;
}
void tree(int u, int pre){
DFS(u, -1);
int centroid = find_centroid(u, -1, sz[u]);
cen[centroid] = 1;
ing[pre].push_back(centroid);
parent[centroid] = pre;
FOA(e, g[centroid]){
int v = e.fs;
if(!cen[v]){
tree(v, centroid);
}
}
}
void update(int u){
int v = u;
while(v != 0){
near[v] = min(near[v], lca.path(u, v));
v = parent[v];
}
}
void del(int u){
int v = u;
while(v != 0){
near[v] = oo;
v = parent[v];
}
}
int query(int u){
int v = u;
int res = oo;
while(v != 0){
res = min(res, near[v] + lca.path(u, v));
v = parent[v];
}
return res;
}
} using namespace Centroid;
signed main(){ quickly
cin >> n >> q;
FOR(i, 1, n - 1){
int u, v, w;
cin >> u >> v >> w;
++u; ++v;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
lca.build(1, -1);
tree(1, 0);
FOR(i, 1, n){
del(i);
}
while(q--){
int s, t;
cin >> s >> t;
vector<int> left, right;
int ans = oo;
FOR(i, 1, s){
int u; cin >> u;
++u;
left.push_back(u);
update(u);
}
FOR(i, 1, t){
int u; cin >> u;
++u;
right.push_back(u);
ans = min(ans, query(u));
}
cout << ans << '\n';
FOA(i, left){
del(i);
}
}
}