本文共 1396 字，大约阅读时间需要 4 分钟。

皇宫看守

Description

太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。

Input

帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。

Output

输入文件中数据表示一棵树，描述如下：

Sample Input

输出文件仅包含一个数，为所求的最少的经费。

Sample Output

6

解题思路

一如既往的树形DP。

#include
   
    #include
    
     using namespace std;long long n,a[1510],b[1510],hd[1510],tot,f[1510][4];struct abc{   	long long to,next;}s[1000010];void add(long long x,long long y){   	s[++tot]=(abc){   y,hd[x]};	hd[x]=tot;}void dp(long long x){   	for(long long i=hd[x];i;i=s[i].next)	{   		long long y=s[i].to;		dp(y);		f[x][1]+=min(f[y][1],min(f[y][2],f[y][3]));		f[x][3]+=f[y][2];	}	f[x][1]+=a[x];	long long tmp=0;	for(long long i=hd[x];i;i=s[i].next)	{   		long long y=s[i].to;		tmp+=min(f[y][1],f[y][2]);	}	f[x][2]=0x3f3f3f3f;	for(long long i=hd[x];i;i=s[i].next)	{   		long long y=s[i].to;		f[x][2]=min(f[x][2],tmp-min(f[y][1],f[y][2])+f[y][1]);	}}int main(){   	cin>>n;	for(long long i=1;i<=n;i++)	{   		long long x,k;		scanf("%lld",&x);		scanf("%lld%lld",&a[x],&k);		for(long long j=1;j<=k;j++)		{   			long long y;			scanf("%lld",&y);			add(x,y);			b[y]=1;		}	}	for(long long i=1;i<=n;i++)		if(!b[i])		{   			dp(i);			cout<
     
      <