Algoogle

Algorithm for Programming Contest

Codeforces 442D Adam and Tree

Category: Codeforces Tag: dp, tree

Adam and Tree

問題概要


根付き木を考える.
木の各辺には色を塗ることができるが, ある頂点に隣接する辺のうち色が被っていいのは1色だけで3つ以上の辺の色が被ってはいけない.
このとき根と各節点をつなぐパスを考えたとき, 出現する色の数をコストとする.
さらにそのような全てのパスのコストの最大値が木のコストになる.
今, 根のみの木があって順に節点を追加していく時, 各節点を追加した直後の木のコストの最小値を求めよ.

解法


ある頂点vに対してその子が根となる部分木のコストを考える.
そうするとその頂点を根とする部分木のコストは子のコストのうち, 大きい2つに依存する.
なぜなら一番大きい子に張る辺とvとvの親を結ぶ辺の色を同じにしないと, 明らかに全体のコストがさらに1大きくなってしまうから. 2番目以降はコスト+1する.
あとはこれを素直に実装すればよい.
毎回の更新で更新がなければそこでうち切ること.

コード


(442D.cpp) download
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
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)

struct node{ int a, b, p, c;};
int N;
node dat[1000010];

void update(int v){
    if(v == 1) return;
    int p = dat[v].p, &a = dat[p].a, &b = dat[p].b;
    if(a != v and b != v and dat[b].c < dat[v].c) b = v;
    if(dat[a].c < dat[b].c) swap(a,b);

    int tmp = dat[p].c;
    dat[p].c = max(dat[a].c+(p==1), dat[b].c+1);
    if(dat[p].c == tmp) return;
    update(p);
}

void solve(){
    dat[0] = (node){0,0,0,-1};
    repi(i,2,N+2){
        cin >> dat[i].p;
        update(i);
        printf("%d ", dat[1].c);
    }
}

int main(){
    cin >> N;
    solve();
    return 0;
}

Comments