洛谷P2458 [SDOI2006]保安站岗 题解（树上dp，巧妙，动态规划，较难）

solution:

$dp\left[u\right]\left[02\right]$dp[u][0 2]

$0:点u处站了一个保安$0:点u处站了一个保安

$dp\left[u\right]\left[0\right]=a\left[u\right]$dp[u][0]=a[u]
$dp\left[u\right]\left[0\right]+=min\left(dp\right[v\left]\right[02\left]\right)$dp[u][0]+=min(dp[v][0 2])

$2:点u处没有站保安，点u靠父亲来安保$2:点u处没有站保安，点u靠父亲来安保
$dp\left[u\right]\left[2\right]+=min\left(dp\right[v\left]\right[01\left]\right)$dp[u][2]+=min(dp[v][0 1])

$1:点u处没有站保安，点u靠某个儿子来安保$1:点u处没有站保安，点u靠某个儿子来安保
$dp\left[u\right]\left[1\right]+=min\left(dp\right[v\left]\right[01\left]\right)$dp[u][1]+=min(dp[v][0 1])
$在计算的时候顺便看一下$在计算的时候顺便看一下
$如果dp\left[u\right]\left[1\right]==sigmadp\left[v\right]\left[1\right]$如果dp[u][1]==sigmadp[v][1]
$找一个最小的dp\left[v\right]\left[0\right]-dp\left[v\right]\left[1\right]$找一个最小的dp[v][0]−dp[v][1]
$dp\left[u\right]\left[1\right]+=dp\left[v\right]\left[0\right]-dp\left[v\right]\left[1\right]$dp[u][1]+=dp[v][0]−dp[v][1]

$答案:min\left(dp\right[root\left]\right[0],dp[root\left]\right[1\left]\right)$答案:min(dp[root][0],dp[root][1])

code:

/*
dp[u][0~2]

0:点u处站了一个保安

dp[u][0]=a[u]
dp[u][0]+=min(dp[v][0~2])

2:点u处没有站保安，点u靠父亲来安保
dp[u][2]+=min(dp[v][0~1])

1:点u处没有站保安，点u靠某个儿子来安保
dp[u][1]+=min(dp[v][0~1])
在计算的时候顺便看一下
如果dp[u][1]==sigma dp[v][1]
找一个最小的dp[v][0]-dp[v][1]
dp[u][1]+=dp[v][0]-dp[v][1]

答案:min(dp[root][0], dp[root][1])
*/ 

#include<cstdio>
#include<vector>
#include<algorithm> 
using namespace std;
int f[1505][5];
int val[1505];
vector<int>e[1505];
void TreeDp(int x,int fa)
{
	f[x][0]=val[x];
	int tag=0;
	int ls=1000000007;
	for(int i=0;i<e[x].size();i++)
	{
	
		int y=e[x][i];
		if(y==fa)continue;
		TreeDp(y,x);
		int tmp=min(f[y][0],f[y][1]);
		f[x][0]+=min(tmp,f[y][2]);
		f[x][2]+=tmp;
		if(f[y][0]<f[y][1])tag++;
		else
		{
			ls=min(ls,f[y][0]-f[y][1]);
		}
		f[x][1]+=tmp;
	}
	if(tag==0)
	{
		f[x][1]+=ls; 
	}
	return ;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int num,m,x;
		scanf("%d",&num);
		scanf("%d",&val[num]);
		scanf("%d",&m);
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&x);
			e[num].push_back(x);
			e[x].push_back(num);
		}
	}
	TreeDp(1,0);
	printf("%d\n",min(f[1][0],f[1][1]));
	return 0;
}