| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 577930 | M_W | Factories (JOI14_factories) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ii pair<int, long long>
using namespace std;
int up[21][500001], lg, timer = 0;
int tin[500001], tout[500001];
long long dist[500001];
vector<ii> adj[500001];
// LCA stuff
void process_lca(int a, int p){
tin[a] = timer++;
for(int i = 1; i <= lg; i++){
up[a][i] = up[up[a][i - 1]][i - 1];
}
for(auto [x, w] : adj[a]){
if(x == p) continue;
dist[x] = dist[a] + w;
process_lca(x, a);
}
tout[a] = timer++;
}
bool is_an(int u, int v){
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v){
if(is_an(v, u)) return v;
for(int i = lg; i >= 0; i--){
if(!is_an(u, v)) u = up[u][i];
}
return up[u][0];
}
long long get_dist(int u, int v){
int lca_uv = lca(u, v);
return - (dist[lca_uv] << 1) + (dist[u] + dist[v]);
}
// Centroid stuff
bool blocked[500001];
int sz[500001], split_node;
int calc_subtree(int a, int p){
sz[a] = 1;
for(auto [x, w] : adj[a]){
if(x == p || blocked[x]) continue;
sz[a] += calc_subtree(x, a);
}
return sz[a];
}
bool get_split(int a, int p, int rt){
int msz = sz[rt] - sz[a];
for(auto [x, w] : adj[a]){
if(x == p || blocked[x]) continue;
msz = max(msz, sz[x]);
if(get_split(x, a, rt)) return true;
}
if(msz <= sz[rt] >> 1){
split_node = a;
return true;
}
return false;
}
int pa[500001];
void build_tree(int a, int p){
calc_subtree(a, p);
get_split(a, p, a);
pa[split_node] = p;
blocked[split_node] = true;
for(auto [x, w] : adj[split_node]){
if(blocked[x]) continue;
build_tree(x, split_node);
}
}
// Actual Problem
int bk[500001], book = 1;
long long d[500001];
void update(int u){
int tmp_u = u;
while(u != -1){
if(bk[u] < book) d[u] = get_dist(tmp_u, u);
else d[u] = min(d[u], get_dist(tmp_u, u));
bk[u] = book;
u = pa[u];
}
}
long long query(int v){
int tmp_v = v; long long ret = LLONG_MAX;
while(v != -1){
if(bk[v] == book) ret = min(ret, d[v] + get_dist(tmp_v, v));
v = pa[v];
}
return ret;
}
int main(){
int N, Q;
scanf("%d %d", &N, &Q); lg = int(ceil(log2(N)));
for(int i = 1; i < N; i++){
int u, v; long long w;
scanf("%d %d %lld", &u, &v, &w);
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
process_lca(0, -1);
build_tree(0, -1);
while(Q--){
int S, T; long long ans = LLONG_MAX;
scanf("%d %d", &S, &T);
while(S--){
int u; scanf("%d", &u);
update(u);
}
while(T--){
int v; scanf("%d", &v);
ans = min(ans, query(v));
}
printf("%lld\n", ans);
book++;
}
}