CF1385 F. Removing Leaves 换根dp

CF1385 F. Removing Leaves 换根dp

题目链接

题意：

给你一棵树，有一种操作，选择k个叶子，若叶子节点的父亲相同，则可删去这k个节点，问你最多能操作多少次。

做法：

这题的官方做法是贪心+bfs，不过用换根dp的方法也是可做的。

• 首先我们常规选择节点1为根节点，跑一遍dfs，主要记录下面这些变量
• dp[i]表示节点i最多能删几个儿子节点，只有该节点能删除全部儿子节点，且儿子节点个数为k的倍数时，当前节点才能成为叶子节点
• tp[i]表示以i为根节点的子树的贡献，即最大操作数

接下来考虑如何换根，我们在dfs的时候传两个参数ddp和ttp,分别表示以父亲节点为根时，父亲节点可删节点数和当前树的最大贡献

现在我们要计算以某儿子节点为根时的最大操作数，那么我们只需要考虑如下调整

• 原儿子节点可删，会对原父亲节点有贡献，于是我们ddp-1，重新计算原父亲节点的贡献
• 原父亲节点可删，现在变成儿子了，那么原儿子节点可删节点数+1，重新计算原儿子节点贡献

这样这题就轻松结束了

代码：

#define fst std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout << std::fixed << std::setprecision(20)
#define le "\n"
#define ll long long 
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+50;
const int mod=998244353;
vector<int> g[N];
int dp[N],tp[N];
int n,k,ans;
int sz = 0,tot = 0;

int dfs(int u,int fa){
    dp[u] = tp[u] = 0;
    for(auto i: g[u]){
        if(i==fa) continue;
        dp[u] += dfs(i,u);
        tp[u] += tp[i];
    }
    tp[u] += dp[u]/k;

    return (dp[u]==g[u].size()-1&&dp[u]%k==0);
}

void dfs1(int u,int fa,int ddp,int ttp){
    ans = max(ans,ttp);
    for(auto i: g[u]){
        if(i==fa) continue;
        int x = ddp,y = ttp;
        if(dp[i]==g[i].size()-1&&dp[i]%k==0) y = y-x/k+(x-1)/k,x--;
        int tmp = dp[i];
        if(x==g[u].size()-1&&x%k==0) y = y-tmp/k+(tmp+1)/k,tmp++;
        dfs1(i,u,tmp,y);
    }
}

void solve(){
    tot++;
    cin>>n>>k;    
    for(int i=1;i<=n;i++){
        g[i].clear();
    }
    for(int i=1;i<n;i++){
        int u,v; cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    ans = 0;
    dfs(1,0);
    dfs1(1,0,dp[1],tp[1]);
    cout<<ans<<le;
}

int main(){
    fst;
    int t; cin>>t;
    sz = t;
    while(t--){
        solve();
    }   
    return 0;
}