백준 19915번 Split the Attractions
센트인 건 알고 풀었다. 어느 정도 접근한 다음에 뭔가 잘 안돼서 인터넷에서 풀이를 보고 풀었다.
algorithm
일반성을 잃지 않고 $a \leq b \leq c$라고 하자. 직관적으로 $c$를 연결되게 하는 것보다는 $a, b$를 연결되게 하는 것이 편하다.
그래프에서 dfs spanning tree를 구성하자. (사실 아무렇게나 구성해도 spanning tree면 상관없다.)그 트리에서 센트로이드를 $cent$라고 하자. $b$는 $cent$를 포함하게 구성한다고 하면 $a$는 원래 그래프에서 $cent$를 포함하지 않고 구성해야 한다. $c$는 남은 위치에 배정하면 된다.
$cent$의 자식 중 원래 그래프에서 서브트리가 서로 연결된 자식끼리 같은 색으로 칠하자. 같은 색인 서브트리를 크기가 큰 순으로 보면서 지금까지 본 서브트리 크기의 합이 $a$보다 커지는 지점에서 멈춘다. 지금까지 본 서브트리를 $a$에 배정하고, 남은 정점은 $c$에 배정하자.
그 후 $cent$ 주변을 $b$에 배정한 후 나머지를 $c$에 배정하면 된다.
만약 크기가 $a$ 이상인 그룹이 존재하지 않는다면 불가능한 경우이다.
proof
만약 크기가 $a$ 이상인 그룹이 존재하지 않는다면 불가능한 경우이다.
$a$에 그룹을 배정하지 않고 배정하는 것이 가능하다고 하자. 그러면 $cent$는 $a$에 배정된다. 하지만 $a \leq b$이므로 $b$는 배정이 불가능하게 된다. 모순이다.
$N - (a \text{에 배정한 서브트리}) \geq b$
각 서브트리의 최대 크기는 센트로이드의 정의에 따라 $\frac{N}{2} $이고 $a \leq b \leq c$ 때문에 $a \leq \frac{N}{3}, b \leq \frac{N-a}{2}$. 그래서 $a$는 최대 $2a$개를 배정할 수 있다. 남은 정점은 $N - 2a$개이고 $b \leq \frac{N-a}{2} \leq N - 2a$를 만족한다.
더 자세한 설명은 구사과님의 블로그를 참조하라.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <bits/stdc++.h>
#include "split.h"
// #include "grader.cpp"
using namespace std;
const int MAXN = 101010;
bool vst[MAXN];
int N, order[3], target[3], sz[MAXN], col[MAXN];
vector<int> ans, g[MAXN], t[MAXN];
void construct_tree(int u)
{
vst[u] = true;
for(auto v : g[u]) {
if(vst[v]) continue;
t[u].push_back(v);
t[v].push_back(u);
construct_tree(v);
}
}
void get_sz(int u, int p)
{
sz[u] = 1;
for(auto v : t[u]) {
if(v == p) continue;
get_sz(v, u);
sz[u] += sz[v];
}
}
int get_cent(int u, int p)
{
for(auto v : t[u]) {
if(v == p) continue;
if(sz[v] > N/2) return get_cent(v, u);
}
return u;
}
void coloring(int u, int color)
{
vst[u] = true;
col[u] = color;
for(auto v : g[u]) {
if(vst[v]) continue;
coloring(v, color);
}
}
void numbering(int u, int p, int num, int alt, int& cnt)
{
if(cnt > 0) ans[u] = num, cnt--;
else ans[u] = alt;
for(auto v : t[u]) {
if(v == p) continue;
numbering(v, u, num, alt, cnt);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
N = n;
order[0] = 1;
order[1] = 2;
order[2] = 3;
target[0] = a;
target[1] = b;
target[2] = c;
if(target[0] > target[1]) swap(target[0], target[1]), swap(order[0], order[1]);
if(target[1] > target[2]) swap(target[1], target[2]), swap(order[1], order[2]);
if(target[0] > target[1]) swap(target[0], target[1]), swap(order[0], order[1]);
int m = p.size();
for(int i = 0; i < m; i++) {
g[p[i]].push_back(q[i]);
g[q[i]].push_back(p[i]);
}
construct_tree(0);
get_sz(0, -1);
int cent = get_cent(0, -1);
get_sz(cent, -1);
vector<tuple<int, int, int>> arr;
memset(vst, 0, sizeof(vst));
vst[cent] = true;
for(auto v : t[cent]) {
if(!vst[v]) coloring(v, v);
arr.emplace_back(col[v], sz[v], v);
}
sort(arr.begin(), arr.end(), greater<>());
ans.resize(N);
bool has_ans = false;
int size = 0;
int color = 0;
vector<int> g1;
for(auto [c, s, v] : arr) {
if(c != color) {
size = 0;
color = c;
g1.clear();
}
size += s;
g1.push_back(v);
if(size >= target[0]) {
for(auto u : g1) {
numbering(u, cent, order[0], order[2], target[0]);
}
has_ans = true;
break;
}
}
if(!has_ans) return ans;
int cnt = target[1] - 1;
ans[cent] = order[1];
for(auto v : t[cent]) {
if(ans[v]) continue;
numbering(v, cent, order[1], order[2], cnt);
}
return ans;
}