較難樹形動态規劃（Vijos 1144 小胖守皇宮/皇宮看守）

Vijos 1144 小胖守皇宮(https://vijos.org/p/1144)

一棵樹上；有邊直接相連的點可以互相望見。每個點都要有人全天候看守，在不同的宮殿安排看守所需的費用不同。要在看守全部點的前提下，使得花費的經費最少。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node
{
    long long x,y,next;
    //x父親y兒子
}a[110000];
long long len,last[110000];
long long v[11000],f[11000][5];
bool bk[11000];
void ins(long long x,long long y)
{
    len++;
    a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;
}
void treedp(int x)
{
    f[x][2]=v[x];f[x][0]=0;f[x][1]=0;
    /*f[x][2]:自己看自己
      f[x][0]:讓自己的兒子來看自己
      f[x][1]:讓自己的父親來看自己
      PS：f數組儲存的都是總費用
    */
    long long minn=999999999;
    bool bkk=false;
    for (int k=last[x];k;k=a[k].next)
    {//周遊一遍
        long long y=a[k].y;
        if (bk[y]==false)
        {
            bk[y]=true;
            treedp(y);
            minn=min(minn,f[y][2]-f[y][0]);
            //尋找代價最小的兒子
            //f[y][2]-f[y][0]計算讓兒子自己看自己的費用
            f[x][0]+=min(f[y][0],f[y][2]);
            if (f[y][2]<=f[y][0]) bkk=true;
            //如果自己看自己的費用總是小于讓兒子來看他的費用，那麼标記一下，不用兒子來看他
            f[x][1]+=f[y][0];//繼承
            f[x][2]+=min(f[y][0],min(f[y][1],f[y][2]));//取最小值
        }
    }
    if (bkk==false) f[x][0]+=minn;
    //如果沒有兒子來看他，那麼讓代價最小的兒子來看着他
}
int main()
{
    long long n;
    scanf("%lld",&n);
    memset(f,0,sizeof(f)); 
    for (int i=1;i<=n;i++)
    {
        long long x,k,m,y;
        scanf("%lld%lld%lld",&x,&k,&m);
        v[x]=k;
        for (int j=1;j<=m;j++)
        {
            scanf("%lld",&y);
            ins(x,y);ins(y,x);  
        }
    }
    long long root=1;
    memset(bk,false,sizeof(bk)); bk[root]=true;
    treedp(root);
    printf("%lld\n",min(f[root][0],f[root][2]));
    return 0; 
}           

如果不分兒子爸爸的情況：（其實都一樣）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
struct node
{
    LL x,y,next;
}a[110000];
LL last[110000],len;
LL f[110000][5],s[110000];
bool bk[110000];
void build (LL x,LL y)
{
    len++;
    a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;
}
/* f[x][0]:不放人，安全
   f[x][1]:不放人，不安全
   f[x][2]:放人，安全
   f[x][3]:放人，不安全（不存在） 
*/  
void treedp(int x)
{
    f[x][2]=s[x];f[x][0]=f[x][1]=0;
    LL minn=1<<20;
    bool bkk=false;
    for (int k=last[x];k;k=a[k].next)
    {
        LL y=a[k].y;
        if (bk[y]==false)
        {
            bk[y]=true;
            treedp(y);
            minn=min(f[y][2]-f[y][0],minn);
            f[x][0]+=min(f[y][0],f[y][2]);
            if (f[y][2]<f[y][0]) bkk=true;
            f[x][1]+=f[y][0];
            f[x][2]+=min(f[y][0],min(f[y][1],f[y][2]));
        }
    }
    if (!bkk) f[x][0]+=minn;
}
int main()
{
    LL n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        int k,m,x,y;
        scanf("%d%d%d",&x,&k,&m);
        s[x]=k;
        for (int j=1;j<=m;j++)
        {
            scanf("%d",&y);
            build(x,y);build(y,x);
        }
    }
    memset(bk,false,sizeof(bk));
    bk[1]=true;
    treedp(1);
    printf("%d",min(f[1][0],f[1][2]));
    return 0;
}