看到题，感觉像树形DP，遂设计DP式子。
\(dp_u\) 表示以 \(u\) 为根的子树内最多能删多少次（不删 \(u\)）。
那么每次子节点到父节点增加的贡献就是 \(\lfloor\frac{子树大小为1的子节点个数}{k}\rfloor\)。
得出式子 \(dp_u = \sum_{v\in son_u} dp_v + (\sum_{v\in son_u} [dp_v \times k=siz_v]) \div k\)。
为方便，我们把 \(\sum_{v\in son_u} [dp_v \times k=siz_v]\) 用 \(sum_u\) 表示。
这是一颗无根树，所以我们进行换根。
设从 \(u\) 换到 \(v\) ，变量 \(x\) 换根前为 \(x_0\) 换根后为 \(x\)。
\(dp_u=dp_{u0}-dp_{v0}-sum_{u0}\div k+(sum_{u0} - [dp_{v0} \times k = siz_{v0} - 1]) \div k\)
\(siz_u=n-siz_{v0}\)
\(siz_v=n\)
\(dp_v = dp_{v0} + dp_u - sum_{v0} \div k + (sum_{v0} + [dp_u \times k = siz_u - 1]) \div k\)
\(sum_v=sum_{v0}+[dp_u\times k = siz_u - 1]\)
虽然这些式子看起来很复杂，但是是因为我写的屎。
这样我们就得到了一个 \(O(n)\) 的解法，虽然 \(1e5\) 没必要。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef unsigned long long ull;
typedef long long ll;
using Pii = pair<int , int>;
using Pll = pair<ll , ll>;
const int N = 2e5 + 5;
constexpr int INF = 0x3F3F3F3F;
constexpr ll INFl = 0x3F3F3F3F3F3F3F3F;
constexpr int P = 1e9 + 7;
#define typ int
#define writesp(x) write(x) , putchar(32)
#define writeln(x) write(x) , putchar(10)
inline char gc(){static char buf[100000] , *p1 = buf , *p2 = buf;return p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 100000 , stdin) , p1 == p2) ? EOF : *p1 ++ ;}
#define getc gc
inline typ read(){typ x = 0; bool f = 0;char ch = getc();while(!isdigit(ch)){f |= (ch == '-');ch = getc();}while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getc();}return (f ? -x : x);}
inline void write(typ x){if(x < 0) putchar('-') , x = -x;if(x / 10) write(x / 10);putchar(x % 10 ^ 48);}
int n , k;
struct edge {
int to , nxt;
}e[N << 1];
int head[N] , cnt = 1;
void adde(int u , int v){
e[ ++ cnt] = {v , head[u]};
head[u] = cnt;
e[ ++ cnt] = {u , head[v]};
head[v] = cnt;
}
void clr(){
cnt = 1;
memset(head , 0 , sizeof head);
}
int dp[N] , siz[N] , sum[N];
void Dp(int u , int fa){
siz[u] = 1;
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa) continue;
Dp(v , u);
siz[u] += siz[v];
dp[u] += dp[v];
sum[u] += (dp[v] * k == siz[v] - 1);
}
dp[u] += sum[u] / k;
}
int ans = 0;
void ch_rt(int u , int fa){
ans = max(ans , dp[u]);
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa) continue;
int dpu = dp[u] - dp[v] - sum[u] / k + (sum[u] - (dp[v] * k == siz[v] - 1)) / k;
int sizu = siz[u] - siz[v];
siz[v] = n;
dp[v] = dp[v] + dpu - sum[v] / k + (sum[v] + (dpu * k == sizu - 1)) / k;
sum[v] += (dpu * k == sizu - 1);
ch_rt(v , u);
}
}
void solve(){
/*INIT*/
clr();
memset(dp , 0 , sizeof dp);
// memset(siz , 0 , sizeof siz);
memset(sum , 0 , sizeof sum);
ans = 0;
n = read() , k = read();
for(int i = 1; i < n; ++ i){
int u = read() , v = read();
adde(u , v);
}
Dp(1 , 0);
ch_rt(1 , 0);
writeln(ans);
}
signed main(){
int T = read();
while(T -- ) solve();
return 0;
}