#include <bits/stdc++.h>
using namespace std;
int n,s[1501],k[1501],r[1501],fa[1501];
int dp[1501][2],ans=100000;
bool vi[1501];
vector <int> re[3001];
void add(int fr,int to)
{
	re[fr].push_back(to);
	re[to].push_back(fr);
}
void dfs(int x)
{
	if (vi[x]==0)
	{
		vi[x]=1;
		int i;
		dp[x][0]=0;
		dp[x][1]=1;
		if (re[x].size()==0) return;
		else
		{
			for (i=0;i<re[x].size();i++)
				{
					dfs(re[x][i]);
					dp[x][0]+=dp[re[x][i]][1];
					dp[x][1]+=min(dp[re[x][i]][1],dp[re[x][i]][0]);
				}
		}
		
	}
}

int main()
{
	int i,j;
	cin>>n;
	for (i=1;i<=n;i++)
	{
		cin>>s[i]>>k[i];
		for (j=1;j<=k[i];j++)
		{
			cin>>r[j];
			add(s[i],r[j]);
		}
	}
	for (i=1;i<=n;i++)
	{
		dfs(i);
		ans=min(ans,min(dp[i][1],dp[i][0]));
		for (j=1;j<=n;j++)
		{
			vi[j]=0;
		}
	}
	cout<<ans;
	return 0;
}

也许又是晚上打的脑子糊涂了

我知道前向星写的不对，故意试试的

看了下题解感觉dp没啥问题啊。比较疑惑的地方在于题解里为什么不用每个节点当成根节点搜一遍，我觉得这和P1352那种明显有根的树不一样吧