https://www.luogu.org/problemnew/show/P2458

五一来临，某地下超市为了便于疏通和指挥密集的人员和车辆，以免造成超市内的混乱和拥挤，准备临时从外单位调用部分保安来维持交通秩序。

已知整个地下超市的所有通道呈一棵树的形状；某些通道之间可以互相望见。总经理要求所有通道的每个端点（树的顶点）都要有人全天候看守，在不同的通道端点安排保安所需的费用不同。

一个保安一旦站在某个通道的其中一个端点，那么他除了能看守住他所站的那个端点，也能看到这个通道的另一个端点，所以一个保安可能同时能看守住多个端点（树的结点），因此没有必要在每个通道的端点都安排保安。

编程任务：

请你帮助超市经理策划安排，在能看守全部通道端点的前提下，使得花费的经费最少。

 

题意：每个点有一个覆盖费用，覆盖一个点可以把它的相邻点也全都覆盖掉，求覆盖整棵树的最小花费。

思路：

对于一棵以x为根的子树,y为x的子结点

设f[x][0]为x这个点放保安（父亲儿子放不放不知道），那么f[x][0]=∑ min(f[y][0],f[y][1],f[y][2]) + cost[x]，因为x放了只需满足x的子树被覆盖就行，可以随便选。

设f[x][2]为x的父亲结点放保安并且x不放，那么f[x][2]=∑ min(f[y][0],f[y][1])，与上一个的区别在于，不能选f[y][2]，因为x不放。

设f[x][1]为x不放，x的儿子放，那么f[x][1]=∑ min(f[y][0],f[y][1])，如果选择的全部都是f[y][1],要再加上min(f[y][0]-f[y][1])

答案是min(f[root][0],f[root][1])

有几个区分的地方：

①最大独立集问题的特点是：选父亲必须不能选儿子（强制），而这道题是选父亲可以选儿子（不强制），做法不同。

②如果每个点权都是单位1，那么可以贪心做，像这题https://blog.csdn.net/Wen_Yongqi/article/details/87173675，点权不同就必须dp了。

这篇讲的非常好：https://www.luogu.org/blog/new2zy/solution-p2458

#include<bits/stdc++.h>
using namespace std;
#define maxn 2000
#define INF 0x3f3f3f3f

int n,cost[maxn],f[maxn][3],root,fa_num[maxn];
vector<int> child[maxn];

int min(int a,int b,int c){return min(min(a,b),c);}

void dfs(int u)
{
	f[u][0]=cost[u];
	f[u][2]=0;
	if(child[u].size()!=0)f[u][1]=0; else f[u][1]=INF;
	bool ok=0;
	for(int i=0;i<child[u].size();i++)
	{
		int v=child[u][i];
		dfs(v);
		f[u][0]+=min(f[v][0],f[v][1],f[v][2]); 
		f[u][2]+=min(f[v][0],f[v][1]);
		if(f[v][0]<=f[v][1])ok=1,f[u][1]+=f[v][0]; else f[u][1]+=f[v][1];
	}
	if(!ok)
	{
		int minn=INF;
		for(int i=0;i<child[u].size();i++)
		{
			int v=child[u][i];
			minn=min(minn,f[v][0]-f[v][1]);
		}
		f[u][1]+=minn;		
	}
}

void input()
{
	int x,y,z;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		scanf("%d",&cost[x]);
		scanf("%d",&y);
		while(y--)
		{
			scanf("%d",&z);
			child[x].push_back(z);
			fa_num[z]++;
		}
	}	
	for(int i=1;i<=n;i++)if(fa_num[i]==0)root=i;
}

int main()
{
	//freopen("input.in","r",stdin);
	input();
	dfs(root);
	cout<<min(f[root][0],f[root][1]);
	return 0;
}