1. \(O(N^2)\) 풀이
먼저 \(O(N^2)\) 풀이를 생각해보자. \(dp[u][k]\) = 정점 \(u\)의 \(k\)번째 자식을 제외하고, 나머지 자식들이 새로운 전선을 시작하여 합한 최솟값이라고 정의해보자. \(dp[u][-1]\)은 어떤 자식도 제외하지 않은 값이다.
어떤 정점 \(u\)에서 시작해서 \(v\)에서 전선이 끝날 수 있는 조건은 \(v\)의 자식이 존재하지 않거나 (case 1), \(v\)의 자식 \(2\)개를 선택하여 전선 사이에서 끝나는 것 (case 2)이다. 아래 그림은 각 케이스를 나타내고 있다.
\(u\)는 \(u\)의 서브트리에서 어떤 한 자식을 골라 쭉 전선을 만들어 가야하고, 전선중 한 자식을 선택한 번호를 \(k\)라고 할 때, \(dp[u][k]\)를 더해주어야 된다. 왜냐하면 \(k\)를 제외한 다른 자식들은 새로운 전선을 시작하여 이어가야 되기 때문이다.
\(u\)에서 시작해서 \(v\)를 끝날 때, 위의 \(dp\) 값과 \(u-v\) 깊이 차이의 제곱을 더해주면 값을 잘 구해줄 수 있다. 그러므로 \(dp\)의 상태 개수는 \(O(N)\)개이고, 부분 문제를 해결하기 위해 \(u\)의 서브트리에 있는 정점들을 dfs로 순회해야 되므로, \(O(N^2)\)에 문제를 해결할 수 있다.
2. \(O(Nlog^3N)\) 풀이
부분 문제를 빠르게 해결할 아이디어를 생각해보자. \(u - v\)를 전선으로 연결하려면 \((d[v] - d[u])^2 + b\) (\(b\)는 경로 중 더해지는 \(dp\)값들의 합이다)이다. 즉 \(x=d[u]\)에 대한 선형 함수로 관찰할 수 있다. 이 선형 함수들을 관리하고 있다면 CHT로 쉽게 값을 찾을 수 있다.
\(b\)들의 값을 구하기 위해서는 서브 트리를 순회할 필요가 있다. 하지만 선형 함수들을 리프 노드부터 관리하면서 올라와 보자. \(u\)에서 필요한 선형 함수들의 집합은 자식 노드들의 선형 함수들의 집합에 특정한 상수를 더한 형태이다.
즉 선형 함수들의 집합을 관리하면 되고, Small To Large 테크닉으로 관리해줄 수 있다. 이 글에서는 CHT를 Lichao Tree로 관리하고 있다. 두 집합을 합칠 때, 각 선형 함수들을 \(y\)축으로 평행 이동해야 되지만, 이것 또한 Lichao Tree에서 잘 구현해줄 수 있다.
리프 노드들부터 선형 함수를 만들어 관리하면 case 1을 고려할 수 있다. 하지만 아래의 케이스는 고려하지 못한다.
case 2에 해당하는 선형 함수가 존재하지 않기 때문에 고려할 수가 없다. case 2에 해당하는 함수는 \((d[u]-x)^2 + b\)이다. \(b\)는 \(u\)의 자식들의 선형 함수들 중에서 \(2\)개를 선택하여 합친 값이다.
자식 \(v_1\)에서 선택한 선형 함수를 \(l_1(x) = -2xd[y_1] + b_{y_1}\), \(v_2\), 선택한 선형 함수를 \(\(l_2(x) = -2xd[y_2] + b_{y_2}\)\)라고 하면 두 선형 함수를 합친 함수는 \(l(x) = (d[y_1]+d[y_2] - 2x)^2 + b_{y_1} + b_{y_2}\)이다. 그러므로 \(b = l(d[u]) + 2x^2 - dp[u][-1] + dp[u][v_1] + dp[u][v_2]\) 가 된다.
\(b\)의 최솟값을 찾으려면 \(O(N^2)\)번의 탐색이 필요하다. 하지만 \(l_1(x), l_2(x)\)와 \(l(x)\)의 차이를 잘 생각해보면 또 CHT를 적용하여 구해줄 수 있다.
선형 함수들의 집합을 합칠 때 작은 집합을 \(S\), 큰 집합을 \(L\)로 정의하자. \(S -> L\)로 합칠 것이다. \(S\)에 있는 선형 함수는 \(l_1\), \(L\)에 있는 함수를 \(l_2\)라고 정의하자.
\(l_1, l_2\)와 \(l\)은 \(l(x) = l_1(x) + l_2(x) + 2d[y_1]d[y_2] - 2xd[y_1] - 2xd[y_2] + 2x^2\) 이 성립 되며 식을 잘 정리하면 \(l(x) = l_1(2x) + l_2(2x-y_1) + 2x^2\)가 된다.
\(l_1\)과 \(x\)는 상수로 볼 수 있으므로, CHT를 사용하여 \(b\)값을 구해줄 수 있다. \(b\)의 나머지 상수 들도 잘 생각해보면 만들어진 선형 함수 집합을 활용하여 구할 수 있다. 그러므로 \(S\)의 집합의 개수만큼 새롭게 선형 함수가 추가된다.
그렇다면 \(O(NlogN)\)의 선형 함수를 관리하며 합칠 때는 \(O(logN)\), 원소를 옮길 때에는 \(O(logN)\)이 소요되므로 \(O(Nlog^3N)\)에 해결할 수 있다. 하지만 \(O(NlogN)\)개의 선형 함수를 만들면서 진행하므로 생각보다 빠르게 작동한다.
3. 소스코드
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
struct Line {
ll a, b;
ll f(ll x) { return a * x + b; }
};
struct Lichao {
struct Node {
ll l, r;
Line line;
};
ll n, psum, ns, ne;
vector<Node> seg;
vector<Line> lines;
void init(int s, int e) {
ns = s, ne = e;
seg.push_back({ -1, -1, {0, inf} });
}
int size() { return lines.size(); }
void insert(int num, int s, int e, Line l) {
Line lo = seg[num].line, hi = l;
if (lo.f(s) > hi.f(s)) swap(lo, hi);
if (lo.f(e) <= hi.f(e)) {
seg[num].line = lo;
return;
}
int mid = s + e >> 1;
if (lo.f(mid) < hi.f(mid)) {
seg[num].line = lo;
if (seg[num].r == -1) {
seg[num].r = seg.size();
seg.push_back({ -1, -1, {0, inf} });
}
insert(seg[num].r, mid + 1, e, hi);
}
else {
seg[num].line = hi;
if (seg[num].l == -1) {
seg[num].l = seg.size();
seg.push_back({ -1, -1, {0, inf} });
}
insert(seg[num].l, s, mid, lo);
}
}
void insert(Line l) {
l.b -= psum;
lines.push_back(l);
insert(0, ns, ne, l);
}
void apply() {
for (auto& l : lines) l.b += psum;
for (auto& l : seg) l.line.b += psum;
psum = 0;
}
ll query(int num, int s, int e, ll x) {
if (num == -1) return inf;
int mid = s + e >> 1;
ll d = seg[num].line.f(x) + psum;
if (x <= mid) return min(d, query(seg[num].l, s, mid, x));
else return min(d, query(seg[num].r, mid + 1, e, x));
}
ll query(ll x) { return query(0, ns, ne, x); }
};
const ll MAX = 50001;
vector<ll> V[MAX], G[MAX], dp[MAX], vec[MAX];
ll n, par[MAX], ind[MAX], dep[MAX];
Lichao li[MAX];
void dfs(int pos, int d = 0, int p = 0) {
par[pos] = p;
dep[pos] = d;
for (ll w : V[pos]) {
if (w == p) continue;
G[pos].push_back(w);
dfs(w, d+1, pos);
}
}
ll pw(ll x) { return x * x; }
void fillDP(int pos) {
ll sum = 0;
for (auto& w : G[pos]) {
ll d = li[w].query(dep[pos]) + pw(dep[pos]);
sum += d;
vec[pos].push_back(d);
}
dp[pos][0] = sum;
for (int i = 1; i <= G[pos].size(); i++)
dp[pos][i] = sum - vec[pos][i - 1];
}
void merge(int pos) {
ll sum = dp[pos][0];
ll x = dep[pos];
vector<Line> newLines;
for (int i = 0; i < G[pos].size(); i++) {
ll w = G[pos][i];
if (li[w].size() <= li[pos].size()) {
li[w].apply();
for (auto& l : li[w].lines) {
ll l1 = l.f(2 * x), c = -sum + dp[pos][i+1] + 4*pw(x);
ll y1 = -l.a / 2;
newLines.push_back({ -2 * x, li[pos].query(2 * x - y1)+l1+c+pw(x)});
}
for (auto& l : li[w].lines) {
l.b += dp[pos][i + 1];
li[pos].insert(l);
}
}
else {
li[w].psum += dp[pos][i + 1];
li[pos].apply();
for (auto& l : li[pos].lines) {
ll l1 = l.f(2 * x), c = -sum + 4 * pw(x);
ll y1 = -l.a / 2;
newLines.push_back({ -2 * x, li[w].query(2 * x - y1)+l1+c+pw(x)});
}
for (auto& l : li[pos].lines)
li[w].insert(l);
swap(li[w], li[pos]);
}
}
for (auto& l : newLines) li[pos].insert(l);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 0; i < n - 1; i++) {
int u, v; cin >> u >> v;
V[u].push_back(v);
V[v].push_back(u);
}
int root = 1;
for (int i = 1; i <= n; i++)
if (V[i].size() == 1) root = i;
dfs(root);
for (int i = 1; i <= n; i++) {
ind[i] = G[i].size();
dp[i].resize(ind[i] + 1, inf);
li[i].init(0, n);
}
queue<int> q;
for(int i=1; i <= n; i++)
if (!ind[i]) {
q.push(i);
dp[i][0] = 0;
li[i].insert({-2*dep[i], pw(dep[i])});
}
while (q.size()) {
int top = q.front(); q.pop();
int t = par[top];
if (--ind[t] == 0) {
q.push(t);
fillDP(t);
merge(t);
}
}
cout << dp[root][0];
return 0;
}
|
cs |
'PS > 백준' 카테고리의 다른 글
[백준 26113] Two Choreographies (0) | 2022.11.22 |
---|---|
[백준 25491] Mexor tree (0) | 2022.09.14 |
[백준 25500] 무자비한 최단 경로 (0) | 2022.09.14 |
[백준 15506] 정원사 (0) | 2021.12.21 |
[백준 20052] 괄호 문자열 ? (0) | 2021.12.21 |