C - 高橋君の給料

[hxrxchang]

https://atcoder.jp/contests/abc026/tasks/abc026_c

問題概要

高橋社長を含むN人の社員がいる会社がある。 高橋社長を含む各社員の給料は

• 部下のいない社員は1
• 部下のいる社員は、部下の中の最高の給料 + 部下の最低の給料 + 1

になる。 高橋社長の給料はいくらか求めよ。

解き方

基本的な木DPでの解き方で、根から葉まで行って帰りがけでその社員が持つ部下の給与がわかるので更新していくとよさそう。 入力が各社員の上司を示してるので分かりにくいが、そこから各社員が持つ部下に変形すれば↑の解き方ができる。

var dp []int
var members [][]int

func solve() {
    n := getInt()
    in := make([]int, n - 1)

    for i := 0; i < n - 1; i++ {
        in[i] = getInt()
    }

    // 自分がどの社員を部下に持つか
    members = make([][]int, n)
    for i := 0; i < len(in); i++ {
        members[in[i] - 1] = append(members[in[i] - 1], i + 1)
    }

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

    fmt.Println(dp[0])
}

func dfs(node, parent int) {
    dp[node] = dp[node] + 1
    mini := BIGGEST
    maxi := 0
    for _, next := range members[node] {
        if next == parent {
            continue
        }
        dfs(next, node)
        mini = min(mini, dp[next])
        maxi = max(maxi, dp[next])
        dp[node] = mini + maxi + 1
    }
}

https://atcoder.jp/contests/abc026/submissions/53566101