题目1077. 皇宫看守题目描述太平王世子事件后陆小凤成了皇上特聘的御前一品侍卫。皇宫各个宫殿的分布呈一棵树的形状宫殿可视为树中结点两个宫殿之间如果存在道路直接相连则该道路视为树中的一条边。已知在一个宫殿镇守的守卫不仅能够观察到本宫殿的状况还能观察到与该宫殿直接存在道路相连的其他宫殿的状况。大内保卫森严三步一岗五步一哨每个宫殿都要有人全天候看守在不同的宫殿安排看守所需的费用不同。可是陆小凤手上的经费不足无论如何也没法在每个宫殿都安置留守侍卫。帮助陆小凤布置侍卫在看守全部宫殿的前提下使得花费的经费最少。输入格式输入中数据描述一棵树描述如下第一行 n表示树中结点的数目。第二行至第 n1 行每行描述每个宫殿结点信息依次为该宫殿结点标号 i在该宫殿安置侍卫所需的经费 k该结点的子结点数 m接下来 m 个数分别是这个结点的 m 个子结点的标号 r1,r2,…,rm。对于一个 n 个结点的树结点标号在 1 到 n 之间且标号不重复。输出格式输出一个整数表示最少的经费。数据范围0 N ≤ 1500 0N≤15000N≤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代码#includebits/stdc.husingnamespacestd;constintN150010,INF0x3f3f3f3f;intn,w[N],f[N][3];//0:选自己,1:选父亲,2:选孩子boolvis[N],has_fa[N];vectorintg[N];voiddfs(intu){vis[u]true;f[u][0]w[u];intdINF;intleng[u].size();for(inti0;ilen;i){intvg[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])d0;elsedmin(d,f[v][0]-f[v][2]);}f[u][2]d;}intmain(){cinn;while(n--){intu,m,v;cinuw[u]m;while(m--){cinv;has_fa[v]true;g[u].push_back(v),g[v].push_back(u);}}introot1;while(has_fa[root])root;dfs(root);coutmin(f[root][0],f[root][2]);return0;}结果