| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1136214 | Sharky | 공장들 (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
#define int long long
#define fi first
#define se second
const int N = 5e5 + 5;
int n, q, sz[N], bl[N], mnd[N];
vector<pair<int, int>> adj[N], anc[N];
bool c[N];
void dfs_sz(int u, int p) {
sz[u] = 1;
for (auto& [v, w] : adj[u]) {
if (v == p || c[v]) continue;
dfs_sz(v, u);
sz[u] += sz[v];
}
}
int dfs_cent(int u, int p, int tot) {
int res = -1, mx = 0;
for (auto& [v, w] : adj[u]) {
if (v == p || c[v]) continue;
res = max(res, dfs_cent(v, u, tot));
mx = max(mx, sz[v]);
}
mx = max(mx, tot - sz[u]);
if (mx <= tot / 2) res = max(res, u);
return res;
}
void redfs(int cent, int u, int p, int dist) {
anc[u].push_back({cent, dist});
for (auto& [v, w] : adj[u]) {
if (v == p || c[v]) continue;
redfs(cent, v, u, dist + w);
}
}
void decomp(int u) {
dfs_sz(u, -1);
int cent = dfs_cent(u, -1, sz[u]);
// debug(cent);
c[cent] = 1;
redfs(cent, cent, -1, 0);
for (auto& [v, w] : adj[cent]) {
if (c[v]) continue;
decomp(v);
}
}
const int inf = 1e18;
void solve() {
cin >> n >> q;
for (int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
u++, v++;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
decomp(1);
for (int i = 1; i <= n; i++) mnd[i] = inf;
// for (int i = 1; i <= n; i++) {
// debug(i);
// debug(anc[i]);
// }
while (q--) {
int s, t;
cin >> s >> t;
vector<int> x(s), y(t);
for (int i = 0; i < s; i++) {
cin >> x[i];
x[i]++;
for (auto& [u, dist] : anc[x[i]]) mnd[u] = min(mnd[u], dist);
}
int ans = inf;
for (int i = 0; i < t; i++) {
cin >> y[i];
y[i]++;
for (auto& [u, dist] : anc[y[i]]) ans = min(ans, mnd[u] + dist);
}
cout << ans << '\n';
for (int i = 0; i < s; i++) {
for (auto& [u, dist] : anc[x[i]]) mnd[u] = inf;
}
}
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int test = 1;
// cin >> test;
while (test--) solve();
}