D - Erase Leaves

[hxrxchang]

https://atcoder.jp/contests/abc333/tasks/abc333_d

問題概要

木がある。 葉(次数が1のノード)のみ消せる。 頂点1を消すのに最短で何回かかるか求めよ。

解き方

頂点1をルートとする木を考える。 頂点1を葉にするには、頂点1を親とする部分木が1個になっていると、頂点1は葉になっていると言える。

上のような木になっていたら、頂点が12個の部分木は残して、残りの部分木を消しに行くのが最小回数で達成できる。 そのため以下の手順で答えが分かる。

1. 各頂点がルートとなる部分木で、それが持つ頂点数を求める。
2. 頂点1が連結している頂点の中で、最も大きい部分木は残しておきたいので、全頂点数 - 最も大きい部分木の頂点数 が答えになる。

var tree [][]int
var dp []int

func solve() {
    n := getInt()
    tree = make([][]int, n)

    for i := 0; i < n-1; i++ {
        in := getInts()
        a, b := in[0]-1, in[1]-1
        tree[a] = append(tree[a], b)
        tree[b] = append(tree[b], a)
    }

    dp = make([]int, n)
    dfs(0, -1)

    maxNodeCnt := 0
    for _, v := range tree[0] {
        maxNodeCnt = max(maxNodeCnt, dp[v])
    }

    fmt.Println(n - maxNodeCnt)
}

func dfs(node, parent int) {
    dp[node] = dp[node] + 1
    for _, next := range tree[node] {
        if next == parent {
            continue
        }
        dfs(next, node)
        dp[node] += dp[next]
    }
}

https://atcoder.jp/contests/abc333/submissions/53558012