ECR158-E Compressed Tree

問題文

https://codeforces.com/contest/1901/problem/E (2200diff)

木が与えられる。各頂点には整数が書き込まれている。

あなたは木に対して回以上以下の操作を行う。

• 次数が以下の頂点を一つ選び、削除する。

全ての操作を終えた後、木が以下のように変化する

• 全ての次数の頂点が削除され、もともとつながっていた両端点が辺で接続される

残った頂点に書き込まれている値の総和(以下スコアと呼ぶ)を最大化せよ

制約

• 
• 

解法

根つき木として考える。親側の頂点を全て消すような頂点を固定する。

を親側の頂点が残っていると仮定した上で頂点を根とした部分木のみのスコアの最大値

とすると、これはいつもの木dpの要領でできる。具体的には子の部分木を個、個、個以上残す場合のスコアの最大値を計算すれば良く、自体は子の部分木を個のみ残すとしたときだけ寄与しない(親が残っているため、)

の親側の頂点を全て消したときのスコアの最大値はの子のの値を用いて計算できる。(計算方法は木dpとほぼ同じ要領)

実装

#include <bits/stdc++.h>

#include "Src/Template/IOSetting.hpp"
using namespace zawa;

long long solve() {
    int n; std::cin >> n;
    std::vector<int> a(n);
    for (auto& x : a) std::cin >> x;
    std::vector<std::vector<int>> g(n);
    for (int _{} ; _ < n - 1 ; _++) {
        int u, v; std::cin >> u >> v;
        u--; v--;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    std::vector<long long> dp(n, (long long)-1e18);
    long long ans{};
    auto rec{[&](auto rec, int v, int p) -> void {
        std::vector<long long> remain(4, (long long)-1e18);
        remain[0] = 0LL;
        for (auto x : g[v]) if (x != p) {
            rec(rec, x, v);
            std::vector<long long> next{remain};
            for (int i{} ; i < 4 ; i++) {
                next[std::min(i + 1, 3)] = std::max(next[std::min(i + 1, 3)], remain[i] + dp[x]);
            }
            remain = std::move(next);
        }
        // 親を消す
        for (int i{} ; i <= 3 ; i++) {
            ans = std::max(ans, (i == 2 ? 0 : a[v]) + remain[i]);
        }
        // 親を残す
        for (int i{} ; i <= 3 ; i++) {
            dp[v] = std::max(dp[v], (i == 1 ? 0 : a[v]) + remain[i]);
        }
    }};
    rec(rec, 0, -1);
    return ans;
}

int main() {
    SetFastIO();

    int t; std::cin >> t;
    while (t--) {
        std::cout << solve() << '\n';
    }
}

感想

バチャ中はなんとなくで木DPをぼんやり考えて全方位がどうとか言って破滅していた。ちゃんと筋道立てて考える努力をしなければいけない。

「根つき木として考える」「親側を消す頂点を全探索」が重要な視点だと思った。