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;
}