题解|皇宫看守

应该都不难看出这是个树形dp吧，那接下来就讲过程了。

状态设置

    我们设置一个dp数组f[i][j]，表示以i为根的树，当前状态为j时设置看守的最小花费。

    a.i表示当前结点的编号。

    b.j表示当前结点的状态，根据题意，只要在某一个结点设置看守，那么它的父亲与儿子也会受到影响。所以对于一个结点,可能会有以下三种情况：1.被它的父亲影响；2.被它自身设置的看守影响；3，被它的某一个儿子影响。

    这样，我们就设好了状态。

状态转移方程

    既然一个结点可能有3种状态，那么我们就对于每一种状态都推一下状态转移方程。

    a.状态1（被它的父亲影响）：

        因为它的父亲已经设置了看守，那么它的儿子可能会被儿子结点自身看到（即f[j][2]，j∈son[j]），也可能被它的儿子的儿子看到（即f[j][3],j∈son[j]）。所以这个状态的转移方程就是f[i][1]=min(f[j][1],f[j][2])(j∈son[i])

    b.状态2（它自身设置看守）

        既然它自身已经设置了看守，那么它的子结点是什么状态就都可以了。

        状态转移方程：f[i][2]=min(f[j][1],f[j][2],f[j][3])+r[i](j∈son[i])

    c.状态3（被它的儿子影响）

        首先，我们先对于它的儿子取与不去先dp一遍，同时记录一个变量d（后面会解释）  f[i][3]=min(f[j][1],f[j][2]),d=min(f[j][2]-min(f[j][1],f[j][2]))(j∈son[i])

        然后，我们再f[i][3]+=d，这里d的作用是强制选择一个花费最小的点，因为在之前的dp时，我们不能确定它的儿子结点有没有被选择。

一些需要注意的地方

    没有，看代码吧

#include<cstdio>
#include<algorithm>
using namespace std;
int f[1510][3];
int n;
int sum[1510];
int head[1510],cnt;
struct edge{
    int nxt,go;
}e[3010];
void add(int u,int v){e[++cnt]=(edge){head[u],v},head[u]=cnt;}
void dfs(int u,int fa)
{
    int ex=0x7fffffff;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].go;
        if(v==fa)
            continue;
        dfs(v,u);
        f[u][0]+=min(f[v][1],f[v][2]);
        f[u][1]+=min(f[v][0],min(f[v][1],f[v][2]));
        f[u][2]+=min(f[v][1],f[v][2]);
        ex=min(ex,-min(f[v][1],f[v][2])+f[v][1]);
    }
    f[u][1]+=sum[u];
    f[u][2]+=ex;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int num,fum,son;
        scanf("%d %d %d",&num,&fum,&son);
        sum[num]=fum;
        for(int j=1;j<=son;j++)
        {
            int v;
            scanf("%d",&v);//注意连两条边
            add(num,v);
            add(v,num);
        }
    }
    dfs(1,-1);
    printf("%d\n",min(f[1][1],f[1][2]));
    return 0;
}