백준11808 마리오와 사악한 키노피오

작성일 | In

문제 링크

  • http://icpc.me/11808

사용 알고리즘

  • 트리 DP

시간복잡도

  • $O(NK^2)$

풀이

$D(v, cnt) := v$를 루트로 하는 서브 트리에서 정점 $cnt$개를 선택해서 방문하면서 마지막에 $v$를 방문하는 최대 거리이라고 정의합시다. $D(v, 0) = D(v, 1) = 0$입니다.
상태 전이는 $v$의 자식 정점 $c$를 차례로 순회하면서, 기존에 본 정점들에서 $cnt-i$개, 새로 추가되는 $c$를 루트로 하는 서브 트리에서 $i$개를 방문하는 경우를 모두 고려하면 됩니다.

기존에 본 정점들 $cnt-i$개를 방문하는 것은 $D(v, cnt-i)$를 보면 되고, 새로 추가되는 $c$ 서브 트리에서 $i$개를 선택해서 돌아다니는 것은 $D(c, i)$를 보면 됩니다. 이제 간선 $e=(v, c)$를 지나는 횟수만 고려하면 됩니다.
$c$ 아래에서 정점을 $i$개 방문하고 $c$ 위에서 정점을 $K-i+1$개 방문하기 때문에, 최대 거리가 되는 방법은 간선 $e=(v, c)$를 $2 \cdot \min(i, K-i+1)$번 방문하는 것이 최적입니다. 그러므로 간선의 비용을 $w$라고 하면, 상태 전이는 $D(v, cnt) \leftarrow D(v, cnt-i) + D(c, i) + 2\cdot w \cdot \min(i, K-i+1)$과 같이 나타낼 수 있습니다.

모든 트리DP는 이진 트리의 관점에서 볼 수 있다는 점을 생각하면 보다 더 쉽게 이해할 수 있을 것입니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using PLL = pair<ll, ll>;

int N, K;
vector<PLL> G[1010];
ll D[1010][1010];

void Init(){
    for(int i=1; i<=N; i++) G[i].clear();
    for(int i=1; i<=N; i++) memset(D[i], -1, sizeof(ll)*(K+1));
}

void DFS(int v){
    D[v][0] = 0;
    D[v][1] = v == 1 ? -1 : 0;
    for(auto [i,w] : G[v]){
        DFS(i);
        for(int cnt=K; cnt>=1; cnt--){
            for(int nxt=1; nxt<=cnt; nxt++){
                if(D[v][cnt-nxt] == -1 || D[i][nxt] == -1) continue;
                D[v][cnt] = max(D[v][cnt], D[v][cnt-nxt] + 2LL*w*min(nxt, K-nxt+1) + D[i][nxt]);
            }
        }
    }
}

void Solve(){
    cin >> N >> K; Init();
    for(int i=2; i<=N; i++){
        int p, w; cin >> p >> w;
        G[p].emplace_back(i, w);
    }
    DFS(1);
    cout << D[1][K] << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    for(int tc=1; tc<=T; tc++){
        cout << "Case " << tc << ": ";
        Solve();
    }
}