终于`\交了11次我晕
自己的方法超恶心\AC了再看题解 哎~牛人真的好多阿``

第六组有问题吗？我也WA在那儿了。

第六组是不是有问题?

點解唔可以f(root, k) , k = 0, 1

f(root, 1)表示放一個在root, f(root, 0)表示不放

f(root, 1) = p(root) + Min { f( son_of(root), 0 or 1 ) }

f(root, 0) = Min{ f( son_of(root), 0 or 1) } , 但至少有一個'1'

且在葉子結點時作特別處理

邊個可以講出有乜問題?

???????????????????????????????

!!!!!!!!!!!!!!!!!!!!!!!

终于会树形DP了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

还可以,程序也就60行

那个大牛给个正确程序看看呀，我使用卑鄙手段过的

树型动态规划

原题意似乎说这棵树节点的父子关系是指定的（也就是一张有向图），不过考虑到父子间可以互相控制，我用的无向图的方法把每条边作双向处理

至于树根就用random随便找了（反正结果都一样）

动态规划就有点恼火了

对于任意i节点可能存在三种状态，用f表示三种状态下各自的最小代价(k=1~3)：

1、当前节点放守卫,受到控制(f)；

2、当前节点不放守卫,受到其子节点控制(f);

3、当前节点不放守卫,也不受其子节点控制(f),此种情况下i节点必然将会被其父节点控制

状态转移方程

1、f=Σmin{f[j,1],f[j,2],f[j,3]|j为i所有子节点编号}+w[i](当前节点放守卫)

2、f=Σmin{f[j,1],f[j,2]|j同上}+dis

(这种情况下要保证i节点不放守卫但受到其子节点控制,必须至少有一个子节点要放守卫,如果所取的最小值全部都是由未放守卫的子节点取得的,就得从中选一个放守卫代价较小的,dis就是这个节点f[j,1]与f[j,2]的差，即dis=min{f[j,1]-min(f[j,1]-f[j,2])})

3、f=Σf[j,2](j同上)

　　一个每条边都是桥的图（即一棵树），对每个顶点进行染色，染色的方法是把

该点和与其有边相连的点全部染上色，但是染色的代价是不一样的，这个代价等于

那个点的某个权值，现用某种方案染色使这个图全部染色，问最少代价。

　　这是一个典型的树形动态规划。“算法与数据结构”网站上有该题的解题报告，

我的方法基本上是根据这个来的，具体的请到该网站查阅。

　　大概思路，分三种情况，某个节点可能的三种情况，一是自己染色，二是由子

节点染色，三是自己不染色，也不由子节点来担心，就把这个任务交给该节点的父

节点了，这三种情况用不同的域来存。

　　第一规划：该节点自己染色，子节点们就用自己三个域中的最小值（想一想为

什么）

　　第二规划：该节点由孩子来染色，但是由哪一个孩子来染色呢？不知道吧，那

就枚举先，枚举子节点作为控制父节点的节点，其他节点全部用作能染色的类型，

累加选最小的。

　　第三规划：自己不染色，孩子也不来，就把这个任务交给父节点，那么该节点

没有染色，该节点的子节点就必须能够自己染色，这种自己染色的情况又有两种，

选一种最小的累加起来。

　　

不知道说的清楚不～～

经典的树型DP

本题既可以用有向树来做,也可以用无向图随机选根结点

分析可见,对于当前结点i,它有num个子结点,它有它有3种状态:

1:在当前位放置守卫的情况(被自己所控制)

2:不在当前位放置守卫,但是它已经被它的子结点所控制

3:不在当前位放置守卫,它还没有被它的子结点所影响(即被其父结点控制)

用f表示结点i的第x种情况:

1情况的值由其子结点的1,2,3情况得到最优

2情况的值由其子结点的1,2情况得到最优

3情况的值只可由其2情况求和.

第2种情况要特别注意,要求它的子结点中必须有一个是1状况的,所以可以先将最小值求和,然后加上这num个子结点中每个的1情况与最优情况的f值之差--most

方程:

f:=Σ(min{f[son[j],1],f[son[j],2],f[son[j],3]})+a[i]

f:=Σ(min{f[son[j],1],f[son[j],2]})+most

f:=Σ(f[son[j],2]), 1

感动。刚开始状态压缩得过于厉害，把正解都减掉了。深刻记忆。

为什么就这样过了

我还没想通呢！！

个人认为难度应该改成2

最基本的树型DP

题目中似乎有个条件没说清楚吧

树中父子节点可以互相看见

别的都不行

哈哈哈哈哈哈

感谢*coolxxx*的题解！！！

水题。亏我当时调了一下午，可惜思路不对
用dfs_not表示当前节点未被保护的情况，dfs_did表示已经被保护的情况，**分类讨论**即可。
```c++
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int n, m, rk[1550], rd[1550];
int dp1[1550], dp2[1550];
struct p {
int to, next;
}edge[4004];
int head[1550], top = 0;
void push(int i, int j)
{
rd[j]++;
edge[++top].to = j;
edge[top].next = head[i];
head[i] = top;
}
int dfs_did(int);
int dfs_not(int);

int dfs_did(int nd)
{
if (dp1[nd] != -1) return dp1[nd];
int ans = rk[nd];
for (int i = head[nd]; i; i = edge[i].next)
ans += dfs_did(edge[i].to);
int a2 = 0;
for (int i = head[nd]; i; i = edge[i].next)
a2 += dfs_not(edge[i].to);
return dp1[nd] = min(ans, a2);
}

int dfs_not(int nd)
{
if (dp2[nd] != -1) return dp2[nd];
int ans = rk[nd];
for (int i = head[nd]; i; i = edge[i].next) {
int to = edge[i].to;
ans += dfs_did(to);
}
dp2[nd] = ans;
for (int i = head[nd]; i; i = edge[i].next) {
int to = edge[i].to;
int a2 = rk[to];
for (int j = head[to]; j; j = edge[j].next)
a2 += dfs_did(edge[j].to);
for (int j = head[nd]; j; j = edge[j].next)
if (j != i) {
a2 += dfs_not(edge[j].to);
}
dp2[nd] = min(dp2[nd], a2);
}
return dp2[nd];
}

int main()
{
memset(rd, 0, sizeof rd);
memset(head, 0, sizeof head);
memset(dp1, -1, sizeof dp1);
memset(dp2, -1, sizeof dp2);
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++) {
int a, to;
cin >> a;
cin >> rk[a];
cin >> m;
for (int j = 1; j <= m; j++) {
cin >> to;
push(a, to);
}
}
int rt = 0;
for (int i = 1; i <= n; i++)
if (rd[i] == 0) {
rt = i;
break;
}
cout << dfs_not(rt) << endl;
return 0;
}