题目：1077. 皇宫看守
题目描述
太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。
皇宫各个宫殿的分布，呈一棵树的形状，宫殿可视为树中结点，两个宫殿之间如果存在道路直接相连，则该道路视为树中的一条边。
已知，在一个宫殿镇守的守卫不仅能够观察到本宫殿的状况，还能观察到与该宫殿直接存在道路相连的其他宫殿的状况。
大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。
可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。
帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。
输入格式
输入中数据描述一棵树，描述如下：
第一行 n，表示树中结点的数目。
第二行至第 n+1 行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号 i，在该宫殿安置侍卫所需的经费 k，该结点的子结点数 m，接下来 m 个数，分别是这个结点的 m 个子结点的标号 r1,r2,…,rm。
对于一个 n 个结点的树，结点标号在 1 到 n 之间，且标号不重复。
输出格式
输出一个整数，表示最少的经费。
数据范围
0 < N ≤ 1500 0<N≤15000<N≤1500
时空限制
1s / 64MB
输入样例
6 1 30 3 2 3 4 2 16 2 5 6 3 5 0 4 4 0 5 11 0 6 5 0输出样例
25代码
#include<bits/stdc++.h>usingnamespacestd;constintN=1500+10,INF=0x3f3f3f3f;intn,w[N],f[N][3];//0:选自己,1:选父亲,2:选孩子boolvis[N],has_fa[N];vector<int>g[N];voiddfs(intu){vis[u]=true;f[u][0]=w[u];intd=INF;intlen=g[u].size();for(inti=0;i<len;i++){intv=g[u][i];if(vis[v])continue;dfs(v);f[u][0]+=min(f[v][0],min(f[v][1],f[v][2]));f[u][1]+=min(f[v][0],f[v][2]);f[u][2]+=min(f[v][0],f[v][2]);//必须要选择其中一个孩子if(f[v][0]<f[v][2])d=0;elsed=min(d,f[v][0]-f[v][2]);}f[u][2]+=d;}intmain(){cin>>n;while(n--){intu,m,v;cin>>u>>w[u]>>m;while(m--){cin>>v;has_fa[v]=true;g[u].push_back(v),g[v].push_back(u);}}introot=1;while(has_fa[root])root++;dfs(root);cout<<min(f[root][0],f[root][2]);return0;}