F

当我告诉我的同学们这题是树形dp时他们都表现出了“树？！下次一定学”的反应。于是这篇题解诞生了。
在我的理解中，树形dp的“树形”就是个“形”，把邻接表和dfs放上去，“树形”就处理完了，内核其实还是dp。
父任务：以父节点为根的树要删多少边。子任务：以子节点为根的树要删多少边。
父任务与子任务的关系（状态转移）：当一个节点作为子节点删边时，若其删掉自己与父节点的公共边，那么当父节点需要删边时就能节省需要删的边；否则，不能节省。所以子节点删边时要尽可能删自己与父节点的公共边。相应的，当一个节点作为父节点时，就必须删掉其子节点们要求删掉的这些公共边。

在AC代码上加了点注释：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int N=1e5+7;
typedef long long ll;
vector<int>G[N];//邻接表
int n,k;
ll ans=0;//int dp[N];因为计算过程中用不到子树需要删除的边的数量，所以我就没开这个dp数组
int dfs(int fa,int now){
    int res=0;
    for(auto son:G[now]){
        if(son==fa)continue;//防止访问时反复横跳
        res+=dfs(now,son);
        //dp[now]+=dp[son];
    }
    ans+=res;//dp[now]+=res;先删掉子节点们要求删的公共边
    int root=G[now].size();//这个变量只是随手取名为root，显然它与“根”没有任何关系
    if(root-res>k){
        ans+=((root-res)-k-1);//dp[now]+=((root-res)-k-1);剩下要删的边中，一条边给父节点删，其他的随便删
        return 1;//需要删掉其与父节点的公共边
    }
    return 0;//不需要删掉其与父节点的公共边
}
void solve(){
    ans=0;
    for(int i=1;i<=n;i++)G[i].clear();
    //for(int i=1;i<=n;i++)dp[i]=0;
    //init
    cin>>n>>k;
    int u,v;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    if(dfs(0,1))++ans;//根节点没父节点,根节点可以随便取 dp[根节点]+=dfs(0,根节点）;
    cout<<ans<<endl;//cout<<dp[根节点]<<endl;
}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
}

题外话：趁着我们学校的大佬去打澳门区域赛，我们队在这场比赛中成为这场比赛中我们学校排名最靠前的队，窃喜。