[CQOI2017] 小Q的棋盘

Whiking · 2024-10-07 20:43:17 · 题解

[CQOI2017] 小Q的棋盘

来一个树上背包的做法。

我们可以先求出一个东西，dp[u]，表示从 u 开始走完子树要最少多少步。

求 dp[u] 是简单的。

再求一个 g[u][k]，表示从 u 开始走 k 步最多走几个点（不用回到 u）。

怎么求这个 g 呢。

发现从一个点开始走 k 步，肯定是走完了若干个子树，然后再走一个子树的一部分。

那么我们可以钦定走了哪个子树的一部分，对其他的子树做背包。

复杂度是 O(n^2k^2)，实际跑得飞快。

#include <bits/stdc++.h>

void Freopen() {
    freopen("", "r", stdin);
    freopen("", "w", stdout);
}

using namespace std;
const int N = 1e2 + 10, M = 2e5 + 10, inf = 1e9, mod = 998244353;

int read( int x = 0) { return cin >> x, x; }

int n, K;

int dp[N], siz[N], f[N];
int g[N][N];
vector< int> G[N], F[N];

void dfs( int u, int fu) {
    int cnt = 0;
    siz[u] = 1;

    for ( auto v : G[u])
        if (v != fu)
            dfs(v, u), F[u].push_back(v), dp[u] += dp[v], cnt ++, siz[u] += siz[v];

    dp[u] += cnt * 2;
}

void solve( int u) {
    for ( auto v : F[u]) solve(v);

    if (! F[u].size()) 
        for ( int k = 0; k <= K; k ++) g[u][k] = 1;
    else {
        for ( int k = 0; k <= K; k ++) {
            for ( auto x : F[u]) {
                for ( int val = 0; val <= k; val ++) f[val] = 0;

                for ( auto v : F[u]) {
                    if (v == x) continue ;

                    for ( int val = k; val >= 0; val --)
                        if (val >= dp[v] + 2)
                            f[val] = max(f[val - dp[v] - 2] + siz[v], f[val]);
                }

//这里是 val - dp[v] - 2，是因为 (u, v) 这条边要被经过 2 次。

                for ( int val = 0; val <= k; val ++) g[u][k] = max(g[u][k], 1 + g[x][k - val - 1] + f[val]);
            }

//这里的 k - val - 1，是因为 (u, x) 这条边要被经过 1 次。

        }
    } 
} 

signed main() {
    ios :: sync_with_stdio(false);

    n = read(), K = read();

    for ( int i = 1; i < n; i ++) {
        int u = read() + 1, v = read() + 1;

        G[u].push_back(v), G[v].push_back(u);
    }

    dfs(1, 0), solve(1);

    cout << g[1][K];
}