[트리에 관하여 1: Tree DP] Square-order tree DP ★

이 블로그의 "트리에 관하여" 시리즈의 첫 번째 카테고리, ❮Tree DP❯에서 다루는 첫 번째 주제이다.

 

이 테크닉은 다른 이름으로도 알려져 있다. KOI에 출제된 어떤 유명한 문제의 이름을 딴 것인데, 스포일러가 될 수 있으므로 연습 문제 목차에서 후술 하겠다.

 

1. 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)$에 해결할 수 있다.

 

2. 정당성

왜 그럴까?

잠시 화면에서 눈을 떼고 직접 그 이유를 찾아보길 권한다.

 

이 테크닉의 정당성을 증명하는 방법을 조합론적 방법과 대수적 방법이 있다. 조합론적 방법이 훨씬 직관적이고 기억하기 편하다. 더 엄밀하게 확인해보고자 하면, 대수적 방법도 확인해 보자.

 

2.1. 조합론적 증명

서로 다른 두 서브트리에서 각각 정점을 하나씩 선택하고 그 둘을 연결하는 경로를 생각하면, 모든 정점 쌍을 돌아보는 것과 같기 때문에 $O(n^2)$이다.

 

2.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)$이라고 가정하고 대입해 보면 수학적 귀납법에 따라 성립함을 확인할 수 있다.

 

3. 연습 문제

3.1. Algorithmic Engagements - Barricades

문제 링크

Looking for a Challenge?의 일부 무료로 공개된 pdf 부분에 Barricades 문제에 대한 꼼꼼하고 시각적인 설명이 있다.

참고로 필자는 직접 풀고서 pdf는 훑어만 봤는데, 꼼꼼하고 시각적이긴 하지만 글이 좀 길어서... 테크닉을 잘 이해했다면 굳이 읽어보지 않아도 될 것 같다.

Barricades Solution.pdf

0.13MB

필자의 코드

      

      

      

    
    

      <cpp />
    
#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);
    }
}

 

3.2. AtCoder Beginner Contest - Components

문제 링크

Barricades보다 조금 더 어렵고 재미있다.

친절한 에디토리얼이 있으니, 역시 따로 풀이를 설명하지는 않는다.

필자의 코드

      

      

      

    
    

      <cpp />
    
#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]));
}

 

3.3. 더 많은 문제들

스포 주의

• 한국정보올림피아드 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

 

3.4. 참고한 글

• https://arnold518.tistory.com/103