求调
查看原帖
求调
953181
Floating_Trees楼主2023/9/29 17:41
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1550;
int n,dp[maxn][2];
vector<int> v[maxn];

void dfs(int u,int fa)
{
	dp[u][1] = 1;
	for (int i = 0;i < (int)v[u].size();i++) if (v[u][i] != fa)
	{
		int to = v[u][i];
		dfs(to,u);
		dp[u][0] += dp[to][1];
		dp[u][1] += min(dp[to][0],dp[to][1]);
	}
}

int main()
{
	scanf ("%d",&n);
	
	for (int i = 1;i <= n;i++)
	{
		int id,k;
		scanf ("%d%d",&id,&k);
		for (int j = 1;j <= k;j++)
		{
			int u;
			scanf ("%d",&u);
			v[id].push_back(u);
			v[u].push_back(id);
		}
	}
	
	dfs(1,0);
	printf ("%d",min(dp[1][0],dp[1][1]));
	
	return 0;
}
2023/9/29 17:41
加载中...