풀이
트리에서 분할정복을 하자!
linear 배열에서의 분할정복은 중앙을 기준으로 좌우로 쪼개어 내려간다.
tree에서의 분할정복도 마찬가지로 중앙을 기준으로 들어가면 된다.
트리에서 중앙은 무엇일까?
트리에 centroid라는 것이 있다.
centroid는 어떤 노드를 의미한다.
트리에서 어떤 정점을 제거하면 여러 subtree가 생기게 된다.
이때 생기는 모든 subtree의 크기가 N/2 이하가 되게하는 정점을 의미한다.
다시 말해, centroid는 제거하였을 때 모든 subtree의 크기 <= 노드 수/2가 되도록 하는 정점을 의미한다.
이 문제를 분할정복으로 풀기 전에 아래의 문제를 먼저 분할정복으로 풀어보자.
=> https://www.acmicpc.net/problem/2003
=> 2003 풀이
두 문제 모두 중앙을 지나는 경우 O(N)을 O(logN)번 계산하여 풀면 된다.
코드
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int n_ = 2e5 + 2;
const int k_ = 1e6 + 2;
const int inf = 0x3f3f3f3f;
int n, k, siz[n_], vst[n_], chk[k_];
struct edg { int idx, dst; };
vector<edg> gph[n_];
int get_size(int now, int prv) {
siz[now] = 1;
for (edg nxt : gph[now]) {
if (nxt.idx == prv || vst[nxt.idx]) {
continue;
}
siz[now] += get_size(nxt.idx, now);
}
return siz[now];
}
int get_cent(int now, int prv, int cap) {
for (edg nxt : gph[now]) {
if (nxt.idx == prv || vst[nxt.idx]) {
continue;
}
if (siz[nxt.idx] > cap) {
return get_cent(nxt.idx, now, cap);
}
}
return now;
}
int calc_ans(int now, int prv, int dst, int dph) {
int ret = inf;
if (dst > k) {
return ret;
}
if (chk[k-dst] != inf) {
ret = chk[k-dst]+dph;
}
for (edg nxt : gph[now]) {
if (vst[nxt.idx] || nxt.idx == prv) {
continue;
}
ret = min(ret, calc_ans(nxt.idx, now, dst+nxt.dst, dph+1));
}
return ret;
}
void update_chk(int now, int prv, int dst, int dph) {
if (dst > k) {
return;
}
chk[dst] = min(chk[dst], dph);
vec.push_back(dst);
for (edg nxt : gph[now]) {
if (vst[nxt.idx] || nxt.idx == prv) {
continue;
}
update_chk(nxt.idx, now, dst+nxt.dst, dph+1);
}
}
int go(int now) {
int cap = get_size(now, -1);
int cent = get_cent(now, -1, cap/2);
int ret = inf;
for (int it : vec) {
chk[it] = inf;
}
vec.clear();
vst[cent] = 1;
chk[0] = 0;
for (edg nxt : gph[cent]) {
if (!vst[nxt.idx]) {
ret = min(ret, calc_ans(nxt.idx, cent, nxt.dst, 1));
update_chk(nxt.idx, cent, nxt.dst, 1);
}
}
for (edg nxt : gph[cent]) {
if (vst[nxt.idx]) {
continue;
}
ret = min(ret, go(nxt.idx));
}
return ret;
}
int main() {
scanf("%d %d", &n, &k);
for (int i = 0; i < n-1; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
gph[u].push_back({ v,w });
gph[v].push_back({ u,w });
}
fill(chk, chk+k+1, inf);
int res = go(0);
printf("%d\n", res != inf ? res : -1);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이