이 블로그의 "트리에 관하여" 시리즈의 첫 번째 카테고리, ❮Tree DP❯에서 다루는 첫 번째 주제이다.
이 테크닉은 다른 이름으로도 알려져 있다. KOI에 출제된 어떤 유명한 문제의 이름을 딴 것인데, 스포일러가 될 수 있으므로 연습 문제 목차에서 후술 하겠다.
Square-order tree DP?
사실 이건 그 자체로 뭔가 해야 하는 테크닉은 아니다.
트리 DP 점화식이 2차원으로 나오고, 전이 과정을 합쳐서 대충 보기에는 $O(n^3)$의 시간 복잡도를 가져야 할 것으로 보이는 후술 할 조건을 만족하는 알고리즘이 사실 $O(n^2)$이라는 더 좋은 시간 복잡도를 갖는다는 사실을 이용하는 테크닉이다.
만족해야 하는 조건은 구한 점화식 $\text{dp}(x,y)$에 대해, $x$가 각 노드를 뜻하고 $y$는 $O\left (|T_x|\right )$ 안에서 정의되며, 전이 과정이 두 형제 노드를 루트로 하는 서브트리를 각 크기의 곱의 시간에 합치는 형태를 갖는 것이다.
엄밀하게는, $T\left(|T_u|\right)=\displaystyle \sum _{c_i,c_{j(\neq i)} \in C_u}O\left (|T_{c_i}|\times |T_{c_j}|\right )$꼴을 띤다는 것이다.
이때 $T\left(|T_u|\right)=O\left(|T_u|^2\right)$가 된다는 점을 이용하여, $O(n^3)$처럼 보이는 몇몇 트리 DP 문제들을 $O(n^2)$에 해결할 수 있다.
정당성
왜 그럴까?
잠시 화면에서 눈을 떼고 직접 그 이유를 찾아보길 권한다.
이 테크닉의 정당성을 증명하는 방법을 조합론적 방법과 대수적 방법이 있다. 조합론적 방법이 훨씬 직관적이고 기억하기 편하다. 더 엄밀하게 확인해보고자 하면, 대수적 방법도 확인해 보자.
조합론적 증명
서로 다른 두 서브트리에서 각각 정점을 하나씩 선택하고 그 둘을 연결하는 경로를 생각하면, 모든 정점 쌍을 돌아보는 것과 같기 때문에 $O(n^2)$이다.
대수적 증명
$\displaystyle \sum _{c_i,c_j \in C_u}O\left (|T_{c_i}|\times |T_{c_j}|\right )=|T_u|\times |T_u|-\sum_{c\in C_u}|T_c|^2$이어서, $T(n)=O(n^2)$이라고 가정하고 대입해 보면 수학적 귀납법에 따라 성립함을 확인할 수 있다.
연습 문제
Algorithmic Engagements - Barricades
Looking for a Challenge?의 일부 무료로 공개된 pdf 부분에 Barricades 문제에 대한 꼼꼼하고 시각적인 설명이 있다.
참고로 필자는 직접 풀고서 pdf는 훑어만 봤는데, 꼼꼼하고 시각적이긴 하지만 글이 좀 길어서... 테크닉을 잘 이해했다면 굳이 읽어보지 않아도 될 것 같다.
필자의 코드
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define mup(x,y) x = min(x,y)
const int N = 3003, K = N;
int n, m;
vector<int> adj[N];
int dp[N][K], sub[N];
void dfs(int s = 1, int e = 0) {
sub[s] = 1;
dp[s][1] = siz(adj[s]);
for (auto u : adj[s]) if (u != e) {
dfs(u,s);
per(x,0,sub[s]+sub[u]) rep(y,max(0,x-sub[s]),min(x,sub[u])) {
mup(dp[s][x], dp[u][y]+dp[s][x-y]-2);
}
sub[s] += sub[u];
}
}
int main() {
scanf("%d", &n);
rep(i,2,n) {
int a, b;
scanf("%d%d", &a, &b);
adj[a].push_back(b);
adj[b].push_back(a);
}
fill(dp[0],dp[N],1e9);
dfs();
scanf("%d", &m);
rep(i,1,m) {
int k, ans = 1e9;
scanf("%d", &k);
rep(j,1,n) mup(ans, dp[j][k]);
printf("%d\n", ans);
}
}
AtCoder Beginner Contest - Components
Barricades보다 조금 더 어렵고 재미있다.
친절한 에디토리얼이 있으니, 역시 따로 풀이를 설명하지는 않는다.
필자의 코드
#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
using namespace std;
#pragma region modnum template from ecnerwala/cp-book
// https://github.com/ecnerwala/cp-book/blob/master/src/modnum.hpp
...
#pragma endregion modnum template
using mint = modnum<998244353>;
const int N = 5003;
int n, sub[N];
mint on[N][N], off[N][N];
mint ON[N], OFF[N];
vector<int> adj[N];
void dfs(int s = 1, int e = 0) {
sub[s] = 1;
for (auto u : adj[s]) if (u != e) {
dfs(u,s), sub[s] += sub[u];
}
on[s][1] = off[s][0] = 1;
int pre_sub = 1;
for (auto u : adj[s]) if (u != e) {
rep(x,0,pre_sub) rep(y,0,sub[u]) {
OFF[x+y] += off[s][x] * (on[u][y]+off[u][y]);
ON[x+y] += on[s][x] * (off[u][y]+on[u][y+1]);
}
pre_sub += sub[u];
swap(ON,on[s]), swap(OFF,off[s]);
fill(ON,ON+pre_sub+sub[u]+1,0);
fill(OFF,OFF+pre_sub+sub[u]+1,0);
}
}
int main() {
scanf("%d", &n);
rep(i,2,n) {
int u, v;
scanf("%d %d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs();
rep(i,1,n) printf("%d\n", int(on[1][i]+off[1][i]));
}
더 많은 문제들
스포 주의
- 한국정보올림피아드 2차 대회 - 검은 돌
- 이 문제의 이름을 따서 한국에서는 "검은 돌 트릭"이라고도 알려져 있다.
- 정당성을 증명하는 과정이 정말 재미있었다.
- 한국정보올림피아드 지역 본선 - 트리분할
- 국제정보올림피아드 - Rivers(나무수송)
- Croatian Open Competition in Informatics - Džumbus
- Croatian Open Competition in Informatics - PERIODNI(주기율표)
- Coder's High Round 2 - 트리의 변화
- 웰노운컵 - 우산
- ICPC 대전 인터넷 예선 - Parents
- ICPC 대전 Regional - Slicing Tree
- Codeforces - Karen and Supermarket
- Codeforces - Vladislav and a Great Legend
- Codeforces - Miss Punyverse
- Codeforces - Ostap and Tree
- Codechef - Painting Tree
