gk的树_牛客博客

求助...不知道dp状态设计错了还是贪心设计的有问题.

$f_{u,0/1}$ 到了u这个节点删不删和它父亲相连的边使得度数都<=k 最少删除多少边. 然后抛出子节点状态更新父亲节点状态.

对于 $f_{u,0}$ 来说它必须删除子节点个数 $- (k - 1)$ ,对于 $f_{u,1}$ 来说它必须删除子节点个数 $- (k)$ .

对于更新可以使用贪心策略,不选 $f_{v,0}$ 就要选 $f_{v,1}$ ,假如我 $f_{v,1}$ < $f_{v,0}$ ,那么我肯定选前k个 $f_{v,1}$ - $f_{v,0}$ 最小的, $f_{v,1}$ > $f_{v,0}$ ,那么还是选前k个 $f_{v,1}$ - $f_{v,0}$ 最小的..

求助不知道哪里错了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int M=2;
const int mod=1e9+7;
int f[N][M];//到了u这个节点删不删和它父亲相连的边 使得度数都<=k 最少删除多少边. 
int n,k;
vector<int>G[N];
struct tx{
	int a,b;
}c[N];

bool cmp(tx A,tx B)
{
	return A.a-A.b<B.a-B.b;
}

void dfs(int u,int fa)
{
	f[u][1]=1;int id=0;
	for(int v:G[u])
	{
		if(v==fa)	continue;
		dfs(v,u);
		c[++id]={f[v][1],f[v][0]};
	}
	sort(c+1,c+1+id,cmp);
//	cout<<"dwad"<<' '<<u<<' '<<id<<endl;
//	for(int i=1;i<=id;i++)
//	{
//		cout<<c[i].a<<' '<<c[i].b<<'\n';
//	}
	if(id<=k-1)
	{
		for(int i=1;i<=id;i++)
		{
			f[u][0]+=min(c[i].a,c[i].b);
			f[u][1]+=min(c[i].a,c[i].b);
		}
	}
	else
	{
		//要删除[id-(k-1)]
		for(int i=1;i<=id-(k-1);i++)
		{
			f[u][0]+=c[i].a;
		}
		for(int i=id-(k-1)+1;i<=id;i++)
		{
			f[u][0]+=min(c[i].a,c[i].b);
		}
		//要删除[id-k]
		for(int i=1;i<=id-k;i++)
		{
			f[u][1]+=c[i].a;
		}
		for(int i=id-k+1;i<=id;i++)
		{
			f[u][1]+=min(c[i].a,c[i].b);
		}
	}
}

void run()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
    	f[i][0]=f[i][1]=0;
    	G[i].clear();
	}
    for(int i=1;i<n;i++)
    {
    	int u,v;
    	scanf("%d%d",&u,&v);
    	G[u].push_back(v);
    	G[v].push_back(u);
	}
	dfs(1,1);
	printf("%d\n",f[1][1]-1);
}

int main()
{
	int T=1;
	cin>>T;
	while(T--)
	{
		run();
	}
	return 0;
}