[luogu]P1272 重建道路 树形dp+背包问题

前言

传送门 :

思路

状态表示:
f [ u ] [ k ] f[u][k] f[u][k]表示以 u u u为根的树中保留 k k k个点需要删除的最小边数

状态转移
f [ u ] [ k ] = m i n ( f [ u ] [ k ] , f [ u ] [ j ] + f [ k − j ] − 2 ) f[u][k] = min(f[u][k],f[u][j]+f[k-j]-2) f[u][k]=min(f[u][k],f[u][j]+f[k−j]−2)

显然我们可以将第二位想象成 背包问题来解决

因为我们在 f [ u ] = 1 f[u]=1 f[u]=1的时候已经计算了一次 1 1 1,第二次再计算 f [ x ] f[x] f[x]的时候重复计算了所以需要减去 2 2 2

Mycode

const int N = 160,INF = 0x3f3f3f3f3f;


int n,p;
vector g[N];
int f[N][N];
int ans;
//f[u][k] 表示以u为根节点 保留k个节点 需要删除最少的边
int deg[N];
void dfs(int u,int fa){
	f[u][1] = deg[u];//全切完只保留自己
	for(auto x : g[u]){
		if(x == fa)continue;
		
		dfs(x,u);
		for(int j = p ; j>=1 ;j -- )
			for(int k = 1;k>n>>p;
	for(int i=1;i>a>>b;
		deg[a] ++ ,deg[b] ++ ;
		g[a].pb(b);g[b].pb(a);
	}
	
	memset(f,0x3f,sizeof f);
	dfs(1,0);
	
	
	for(int i=1;i