本蒟蒻做这题的时候 yy 了一个类似换根 DP 的做法，不知有没有大佬来看一下正确性如何，如果以下做法本质上不是换根 DP ，麻烦提醒一下。

设 $f(u,i)$ 表示包含 $u$ 的有 $i$ 个结点的连通块需要割掉的最少边数。

那么有一下情况：

1. 割掉 $u$ 与其父亲 ${\rm fa}(u)$ 的边
2. 不割掉 $u$ 与其父亲的边

表达式如下：

if(fa[u] > 0)
	{
		f[u][siz[u]] = min(f[u][siz[u]],1);//割断这条边 
		for(int i = siz[u] + 1;i <= N;i ++)
		{
			f[pre][i - siz[u]] = min(f[pre][i - siz[u]],f[pre][i] + 1);//割断这条边 
			f[u][i] = min(f[u][i],f[pre][i]);//不割断这条边 
		}
	}

其中 $siz(u)$ 表示以 $u$ 为根的子树大小。

当进行一次换根 DP 的时候，有可能有一些结点没有得到完全更新，但是可以得到 94pts 的好成绩，于是我在程序中进行了两次换根 DP ，然后就水过了本题的数据。

到底是本题数据太水？还是确实存在一种换根 DP 的做法？或者如果以上做法有一定正确性，但是要进行多次换根 DP 的过程，那么如何确定要做多少次换根 DP 才能确保正确？

完整代码如下：

#include<iostream>
#include<cstdio>

using namespace std;
const int inf = 0xfffffff;
int N,P,fa[205],siz[205],f[205][205],head[205];
int cnt,ans = inf,x,y;
struct edge{
	int nxt;
	int to;
}e[350];

void addedge(int from,int to)
{
	cnt ++;
	e[cnt].nxt = head[from];
	e[cnt].to = to;
	head[from] = cnt;
	cnt ++;
	e[cnt].nxt = head[to];
	e[cnt].to = from;
	head[to] = cnt;
	return ;
}

void dfs1(int u,int pre)
{
	siz[u] = 1;
	for(int i = head[u],v= 0;i; i =e[i].nxt)
	{
		v = e[i].to;
		if(v == pre) continue;
		fa[v] = u;
		dfs1(v,u);
		siz[u] += siz[v];
	}
	return ;
}

void dfs2(int u,int pre)
{
	if(pre > 0)
	{
		f[u][siz[u]] = min(f[u][siz[u]],1);//割断这条边 
		for(int i = siz[u] + 1;i <= N;i ++)
		{
			f[pre][i - siz[u]] = min(f[pre][i - siz[u]],f[pre][i] + 1);//割断这条边 
			f[u][i] = min(f[u][i],f[pre][i]);//不割断这条边 
		}
	}
	for(int i = head[u],v = 0;i;i = e[i].nxt)
	{
		v = e[i].to;
		if(v == pre) continue;
		dfs2(v,u);
	}
	return ;
}

int main()
{
	scanf("%d%d",&N,&P);
	for(int i = 1;i < N;i ++)
	{
		scanf("%d%d",&x,&y);
		addedge(x,y);
	}
	dfs1(1,0);
	for(int i = 1;i <= N;i ++)
		for(int j = 0;j <= N;j ++)
			f[i][j] = inf;
	for(int i = 1;i <= N;i ++) f[i][N] = 0;
	f[1][N] = 0;
	dfs2(1,0);//
	dfs2(1,0);//两次换根 DP
	for(int i = 1;i <= N;i ++) ans = min(ans,f[i][P]);
	printf("%d",ans);
	return 0;
}