問題概要

下の図のような木を「ユ木」と呼ぶ（正式な定義は問題文参照）。

頂点数 $N$ の木が与えられ、いくつかの頂点を削除して「ユ木」にしたい。削除する頂点の個数の最小値を求めよ。

制約

$3 \le N \le 3 \times 10^{5}$

考えたこと

与えられた木において、どの頂点を「ユ木の中心」にするかで場合分けして考えることにした。

ユ木の中身にする頂点を $v$ として、 $v$ に隣接する頂点の個数を $K$ として、それらの頂点の次数を $d_{1}, d_{2}, \dots, d_{K}$ とする。このとき、もとの問題は次のように再解釈できる。

$d_{1}, d_{2}, \dots, d_{K}$ からいくつか選び（ $L$ 個とする）、それらの最小値を $M$ とするとき、 $LM + 1$ の値の最大値を求めよ

ここで、ユ木の頂点数は $LM + 1$ となることに注意しよう。この問題は、

$d_{1}, d_{2}, \dots, d_{K}$ を大きい順にソートする
$L = 1, 2, \dots, K$ に対して、 $L \max(d_{1}, d_{2}, \dots, d_{L}) + 1$ の値を求めて、その最大値を求める

という方法で解ける。この計算量は $O(K \log K)$ である。

各頂点 $v$ に対する $K$ の値の総和は $O(N)$ であるから、全体の計算量は $O(N \log N)$ と評価できる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N, u, v;
    cin >> N;
    vector<vector<long long>> tree(N);
    vector<long long> deg(N, 0);
    for (int i = 0; i < N-1; i++) {
        cin >> u >> v, u--, v--;
        tree[u].push_back(v);
        tree[v].push_back(u);
        deg[u]++, deg[v]++;
    }

    long long res = N;
    for (int v = 0; v < N; v++) {
        vector<long long> d, sum;
        for (auto to : tree[v]) d.push_back(deg[to]);
        sort(d.begin(), d.end(), greater<long long>());

        // vec のうち、上位 i 個を残すのを全探索
        for (int i = 1; i <= d.size(); i++) {
            long long num = d[i-1] * i + 1;
            res = min(res, N - num);
        }
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 385 E - Snowflake Tree (1D, 水色, 450 点)

問題概要

制約

考えたこと

コード