#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 1550;
int n, cost[maxn], dp[maxn][3];
bool root[maxn];
vector<int> G[maxn];

void dfs(int u) {
    int _min = 0x3f3f3f3f;
    for (int v : G[u]) {
        dfs(v);
        dp[u][0] += min(min(dp[v][0], dp[v][1]), dp[v][2]);
        dp[u][1] += min(dp[v][0], dp[v][1]);
        dp[u][2] += min(dp[v][0], dp[v][1]);
        _min = min(_min, dp[v][0] - min(dp[v][0], dp[v][1]));
    }
    dp[u][0] += cost[u];
    dp[u][1] += _min;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int u, c, m, v;
        cin >> u >> c >> m;
        cost[u] = c;
        while (m--) {
            cin >> v;
            root[v] = true;
            G[u].push_back(v);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!root[i]) {
            dfs(i);
            cout << min(dp[i][0], dp[i][1]) << endl;
            break;
        }
    }
    return 0;
}

f[0][x] 表示以x为根的子树已经被控制好，且x也被控制好，x放守卫。
f[1][x] 表示以x为根的子树已经被控制好，且x也被控制好，x不放守卫。
f[2][x] 表示以x为根的子树已经被控制好，但x没有被控制,且x不放守卫。
f[0][x]=∑min{f[0][y],f[1][y],f[2][y]}+a[x]; (y是x的直系儿子节点)
f[1][x]=∑min{f[0][y],f[1][y]}+(f[0][u]-f[1][u]);右半部分括号内的东西在y全都不放守卫时起作用。且(f[0][u]-f[1][u])min;
f[2][x]=∑f[1][y];

根节点没有父亲，因此取最小值只能去儿子和自己的

树形DP+邻接表，没有用二叉链表结构，直接多叉树求解

#include<cstdio>
#include<iostream>
#include<cstring>
#define MAXN 1501
#define INF 2100000000
using namespace std;

int n, c[MAXN];
int from[MAXN], to[MAXN], first[MAXN], nxt[MAXN];
int indeg[MAXN] = {0};
int dp[MAXN][3] = {0};

// 0->son, 1->self, 2->pa

void dfs(int i){
    int e = first[i];
    int sonmin, selfmin, pamin, diffmin;
    diffmin = INF;
    while(e){
        dfs(to[e]);
        sonmin = selfmin = pamin = INF;
        selfmin = min(selfmin, dp[to[e]][0]);
        selfmin = min(selfmin, dp[to[e]][1]);
        selfmin = min(selfmin, dp[to[e]][2]);
        dp[i][1] += selfmin;
        sonmin = min(sonmin, dp[to[e]][0]);
        sonmin = min(sonmin, dp[to[e]][1]);
        diffmin = min(diffmin, dp[to[e]][1]-sonmin);
        dp[i][0] += sonmin;
        dp[i][2] += sonmin;
        e = nxt[e];
    }
    dp[i][0] += diffmin;
    dp[i][1] += c[i];
    // cout << endl << i << " : " << dp[i][0] << " " << dp[i][1] << " " << dp[i][2] << endl;
    return;
}

int main(){
    int ti, tn, tto, mcnt = 0, t;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> ti;
        cin >> c[ti];
        cin >> tn;
        for(int j=0; j<tn; j++){
            mcnt ++;
            cin >> tto;
            from[mcnt] = ti;
            to[mcnt] = tto;
            t = first[ti];
            first[ti] = mcnt;
            nxt[mcnt] = t;
            indeg[tto]++;
        }
    }
    int gans = 0;
    for(int i=1; i<=n; i++){
        if(!indeg[i]){
            memset(dp, 0, sizeof(dp));
            dfs(i);
            gans += min(dp[i][0], dp[i][1]);
        }
    }
    cout << gans << endl;

    return 0;
}

评测情况

 Accepted
#   状态  耗时  内存占用
#1  Accepted    3ms     340.0 KiB
#2  Accepted    3ms     372.0 KiB
#3  Accepted    4ms     356.0 KiB
#4  Accepted    4ms     504.0 KiB
#5  Accepted    7ms     352.0 KiB
#6  Accepted    6ms     376.0 KiB
#7  Accepted    3ms     352.0 KiB

dp................
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;
const int N=1505;
int n,a[N],nums[N],son[N][N],f[N][3];
bool v[N];

void dp(int root)
{
int tmp;
if(nums[root]==0) return;
for(int i=1;i<=nums[root];i++) dp(son[root][i]);
tmp=1000000;
for(int i=1;i<=nums[root];i++)
{
f[root][0]=f[root][0]+min(min(f[son[root][i]][0],f[son[root][i]][1]),f[son[root][i]][2]);
f[root][1]=f[root][1]+min(f[son[root][i]][0],f[son[root][i]][1]);
if(f[son[root][i]][0]-min(f[son[root][i]][0],f[son[root][i]][1])<tmp)
tmp=f[son[root][i]][0]-min(f[son[root][i]][0],f[son[root][i]][1]);
f[root][2]=f[root][2]+f[son[root][i]][1];
}
f[root][0]=f[root][0]+a[root];
f[root][1]=f[root][1]+tmp;
}

int main()
{
//freopen("guard.in","r",stdin);
//freopen("guard.out","w",stdout);
int x,d,k,root;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&x,&d,&k);
a[x]=d;
nums[x]=k;
for(int j=1;j<=k;j++)
{
scanf("%d",&son[x][j]);
v[son[x][j]]=1;
}
}
for(int i=1;i<=n;i++)
if(!v[i])
{
root=i;
break;
}
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
if(nums[i]==0)
{
f[i][0]=a[i];
f[i][1]=1000000;
f[i][2]=0;
}
dp(root);
cout<<min(f[root][0],f[root][1])<<endl;
//fclose(stdin);
//fclose(stdout);
return 0;
}

#include <cstdio>
#include <cstdlib>
#define maxn 1510
typedef struct node
{
                int v;
                struct node *next;
}poi;

int n,father[maxn],a[maxn],root,f[3][maxn];
poi *l[maxn],*r[maxn];

poi *newnode()
{
                poi *u=(poi*) malloc(sizeof(poi));
                u->next=NULL;
                return u;
}

void input_data()
{
                scanf("%d",&n);
                for (int i=1;i<=n;i++)
                                l[i]=r[i]=newnode(),father[i]=i;
                for (int i=1;i<=n;i++)
                                {
                                                int x,y,w,num;
                                                scanf("%d%d%d",&x,&w,&num);
                                                a[x]=w;
                                                for (int j=1;j<=num;j++)
                                                                {
                                                                                scanf("%d",&y);
                                                                                r[x]=r[x]->next=newnode();
                                                                                r[x]->v=y;
                                                                                father[y]=x;
                                                                }
                                }
}

int search_father(int x)
{
                if (father[x] !=x)
                                return (search_father(father[x]));
                                                else return x;
}

int min(int a,int b)
{
                return a>b?b:a;
}
/*
                f[0][x] 表示以x为根的子树已经被控制好，且x也被控制好，x放守卫。
                f[1][x] 表示以x为根的子树已经被控制好，且x也被控制好，x不放守卫。
                f[2][x] 表示以x为根的子树已经被控制好，但x没有被控制,且x不放守卫。
                f[0][x]=∑min{f[0][y],f[1][y],f[2][y]}+a[x]; (y是x的直系儿子节点)
                f[1][x]=∑min{f[0][y],f[1][y]}+(f[0][u]-f[1][u]);右半部分括号内的东西在y全都不放守卫时起作用。且(f[0][u]-f[1][u])min;
                f[2][x]=∑f[1][y];
*/
void cm(int x)
{
                poi *p=l[x]->next;
                bool bo=false;
                int special=10000;
                while (p!=NULL)
                                {
                                                int y=p->v;
                                                if (y!=x)
                                                                {
                                                                                cm(y);
                                                                                f[0][x]+=min(f[0][y],min(f[1][y],f[2][y]));
                                                                                if (f[0][y]<=f[1][y]) bo=true;
                                                                                if (special>f[0][y]-f[1][y]) special=f[0][y]-f[1][y];
                                                                                f[1][x]+=min(f[0][y],f[1][y]);
                                                                                f[2][x]+=f[1][y];
                                                                }
                                                p=p->next;
                                }
                if (!bo) f[1][x]+=special;
                f[0][x]+=a[x];
}

int main()
{
                input_data();
                root=search_father(n);
                cm(root);
                printf("%d\n",min(f[1][root],f[0][root]));
                return 0;
}

链式前向星+动态规划。有点坑。看代码注释去。
```cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <climits>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
#include <ctime>
#include <string>
#include <cstring>
using namespace std;
#define INF 100000000
//不用数了，上面是1亿，9位，8个0.
int to[3001],pre[6001],last[6001];//链式前向星各数组
int dp[3001][3];//f(i,j)对于编号i的点，j=0表示由子节点守卫时最小花费，j=1表示由自己守卫最小花费，j=2表示由父节点守卫最小花费
int cost[3001];//顾名思义
int id=0;//给边编号用
void add(int a,int b)//连一条a->b的单向线
{
pre[++id]=last[a];//标记同样由a出发的上一条边是哪条
to[id]=b;//标记这条边连向b
last[a]=id;//标记最后一条边为这条边
}
void dfs(int now,int father)
{
dp[now][1]=cost[now];
dp[now][2]=0;
//上为初始化
int flag=INF;//flag是精华！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
for(int i=last[now]; i; i=pre[i]) {//枚举以now这个点为起点的每一条边
if(to[i]!=father) {//如果某一个点和他连接又不是父节点，那就是子节点。
dfs(to[i],now);//要由叶子节点推到根节点。dfs下一层

dp[now][0]+=min(dp[to[i]][1],dp[to[i]][0]);
//前者优时，状态确定。父节点(to[i])更划算，守卫！
//当后者优时，状态不确定：now让子节点守护，这个子节点又让子节点守护，不清真！
dp[now][1]+=min(dp[to[i]][1],min(dp[to[i]][2],dp[to[i]][0]));//状态确定。
dp[now][2]+=min(dp[to[i]][0],dp[to[i]][1]);//状态确定。
//以下处理dp[now][0]巨坑。
if(dp[to[i]][1]<=dp[to[i]][0]) //now节点的这个儿子自己有了守卫（同时守卫了now）,不用强迫放置守卫于某个子节点(to[i])
flag=0;
if(flag&&dp[to[i]][1]-dp[to[i]][0]<flag) {
//万一父节点没放(to[i])可能要必须放（出现dp[now][0]求值时min函数中后者优的情况，
//必须有一个子节点(to[i])来保护父节点(now)），记录放父节点和原来所增加的额外费用。
//（当然如果某个子节点已经保护了，补差价0元：不用强迫放置守卫于子节点(to[i])）
//如果都没保护父节点(now)，挑一个最划算的，补最小的差价，差价最小多少？没错，在flag里。
flag=dp[to[i]][1]-dp[to[i]][0];//得出：子节点(to[i])自己守卫 & 子节点(to[i])由其子节点(to[i]的子节点)守卫 的差价。 强行放守卫贵了flag这么多。
}
}
}
dp[now][0]+=flag;//补差价
}
int main()
{
int n;
scanf("%d",&n);//n个节点
for (int i=1;i<=n;i++) {
int a,b,k;
scanf("%d",&a);//节点编号
scanf("%d",&cost[a]);//节点放置守卫经费
scanf("%d",&k);//子节点数
while(k--) {
scanf("%d",&b);//子节点
add(a,b);//a->b
add(b,a);//b->a
//子节点父节点连边，注意双向
}
}
dfs(1,0);//作用：由下往上推，最后守卫网络将覆盖到编号为1的点（根节点） ，搞到这时的最小花费 。第二个参数为父节点，根节点（节点1）无父节点，传入0.
printf("%d",min(dp[1][0],dp[1][1]));//输出，没有dp[1][2]，因为根节点没有父亲
return 0;
}

为了练习左子右兄法叫了好多次才发现错在哪里。。。
果然还是太弱了。。。
下面是核心：
void dp(int x)
{
if(x==0)return ;
int l=ch[x][0],r=ch[x][1];
dp(l);dp(r);
f[x][0][0]=f[l][1][0]+min(f[r][0][0],f[r][1][0]);
f[x][1][0]=min(f[l][1][0]+f[r][1][0] , min(f[l][1][1],f[l][0][1])+min(f[r][0][0],f[r][1][0])+v[x]);
f[x][0][1]=min(f[l][1][0],f[l][0][0])+min(f[r][0][1],f[r][1][1]);
f[x][1][1]=min(min(f[l][1][0],f[l][0][0])+f[r][1][1] , min(f[l][1][1],f[l][0][1])+min(f[r][0][1],f[r][1][1])+v[x]);
}

不知道为什么一直过不了，希望能够帮忙看一下。
写的不算很丑，希望能认真的看一下。
thanks~
pascal
var
f:array[0..1500,0..2] of longint;
a:array[0..1500,0..1500] of longint;
w:array[0..1500] of longint;
n,i,j,k,m,x,root:longint;
function min(a,b:longint):longint;
begin
if a=0 then min:=b
else if b=0 then min:=a
else if a<b then min:=a
else min:=b;
end;
procedure dp(u:longint);
var
mm,i,v:longint;
begin
f[u,0]:=w[u]; mm:=maxlongint;
if a[u,0]=0 then exit;
for i:=1 to a[u,0] do
begin
v:=a[u,i];
dp(v);
f[u,0]:=f[u,0]+min(f[v,0],min(f[v,1],f[v,2]));
f[u,1]:=f[u,1]+min(f[v,0],f[v,1]);
f[u,2]:=f[u,2]+f[v,1];
mm:=min(mm,f[v,0]-f[v,1]);
end;
if mm>0 then f[u,1]:=f[u,1]+mm;
end;
begin
readln(n); root:=0;
for i:=1 to n do
begin
root:=root+i;
read(k,w[k],m);
for j:=1 to m do
begin
read(x);
inc(a[k,0]);
a[k,a[k,0]]:=x;
root:=root-x;
end;
readln;
end;
dp(root);
writeln(min(f[root,0],f[root,1]));
end.


看到各位dalao都用了dfs，嵌套循环的我瑟瑟发抖
```c++
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
struct line
{
int to,ne;
}st[1500];
long long a[1501],dp[1501][3];
int n,p,no,h[1501],s[1501],f[1501],vis[1501],ss[1501];
void add(int x,int y)
{
st[++p].to=y;
st[p].ne=h[x];
h[x]=p;
}
int main()
{

scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&no);
scanf("%lld%d",&a[no],&s[no]);
ss[no]=s[no];
for(int j=1;j<=s[no];j++)
{
int x;
scanf("%d",&x);
add(no,x);
vis[x]=1;
f[x]=no;
}
}
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
f[i]=0;
memset(vis,0,sizeof(vis));
break;
}
}
for(int j=1;j<=n;j++)
{
if(!ss[j])
{
dp[j][1]=a[j];
dp[j][0]=1e15+10;
dp[j][2]=0;
ss[f[j]]--;
vis[f[j]]=1;
ss[j]--;
}
}
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
for(int j=1;j<=n;j++)
{
if(f[j]==0&&ss[j]==-1)
{
printf("%lld",min(dp[j][0],dp[j][1]));
return 0;
}
if(ss[j]==0&&vis[j]==0)
{
int yes=1;
if(h[j]!=0)
yes=0;
for(int ii=h[j];ii;ii=st[ii].ne)
{
if(dp[st[ii].to][1]<=dp[st[ii].to][0])
yes=1;
dp[j][2]+=min(dp[st[ii].to][0],dp[st[ii].to][1]);
dp[j][1]+=min(dp[st[ii].to][0],min(dp[st[ii].to][1],dp[st[ii].to][2]));
}
dp[j][1]+=a[j];
dp[j][0]=dp[j][2];
if(!yes)
{
long long mi=1e15+10;
for(int ii=h[j];ii;ii=st[ii].ne)
{
mi=min(mi,dp[st[ii].to][1]-dp[st[ii].to][0]);
}
dp[j][0]+=mi;
}
ss[f[j]]--;
vis[f[j]]=1;
ss[j]--;

}
}
}
return 0;
}
```

#include <stdio.h>
using namespace std;
int n;
struct node
{
    int fa;
    long long value;
    int childs;
    int child[1501];
};
node tree[1501];
long long f[1501][4];
int visited[1501];
int t[1501];
int root;
int abs(int a)
{
    if (a<0)
    return -a;
    else return a;
}
int min(int a,int b)
{
    if (a<b)
    return a;
    else return b;
}
void dp(int now)
{
    if (visited[now]==1||tree[now].childs==0) return;
    visited[now]=1;
    for (int i=1;i<=tree[now].childs;i++)
    dp(tree[now].child[i]);
    int temp=0;
    f[now][1]=tree[now].value;
    int minn=1000000;
    for (int i=1;i<=tree[now].childs;i++)
    {
        f[now][3]=f[now][3]+f[tree[now].child[i]][2];
        f[now][1]=f[now][1]+min(min(f[tree[now].child[i]][1],f[tree[now].child[i]][2]),f[tree[now].child[i]][3]);
        if (f[tree[now].child[i]][1]<=f[tree[now].child[i]][2])
        {
            temp=1;
            f[now][2]=f[now][2]+f[tree[now].child[i]][1];
        }
        else f[now][2]=f[now][2]+f[tree[now].child[i]][2];
        minn=min(minn,abs(f[tree[now].child[i]][1]-f[tree[now].child[i]][2]));
    }
    if (temp==0)
    f[now][2]=f[now][2]+minn;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        int t1,t2,t3;
        scanf("%d%d%d",&t1,&t2,&t3);
        tree[t1].value=t2;
        tree[t1].childs=t3;
        for (int j=1;j<=t3;j++)
        {
            int temp;
        scanf("%d",&temp);
        tree[temp].fa=i;
        tree[t1].child[j]=temp;
        t[temp]=1;
        }
    }
    for (int i=1;i<=n;i++)
    if (t[i]==0)
    root=i;
    for (int i=1;i<=n;i++)
    if (tree[i].childs==0)
    {
        f[i][1]=tree[i].value;
        f[i][2]=10000000;
        f[i][3]=0;
    }
    dp(root);
    printf("%d\n",min(f[root][1],f[root][2]));

    return 0;
}

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=1500+10;
typedef long long ll;
int last[N],n,len;
ll dp1[N],dp2[N],dp3[N],w[N];

struct Edge{int to,next;Edge(int to=0,int next=0):to(to),next(next){}}e[N<<1];
void add_edge(int u,int v){e[++len]=Edge(v,last[u]);last[u]=len;}
void dp(int x,int fa)
{
    ll mn=(1<<30);
    dp1[x]=dp2[x]=dp3[x]=0;
    for(int i=last[x];i;i=e[i].next)
    {
        int id=e[i].to;
        if(id==fa)continue;
        dp(id,x);
        dp1[x]+=min(dp1[id],min(dp2[id],dp3[id]));
        dp2[x]+=min(dp1[id],dp2[id]);
        ll t=dp1[id]-min(dp1[id],dp2[id]);
        mn=min(mn,t);
        dp3[x]+=min(dp1[id],dp2[id]);
    }
    dp2[x]+=mn;dp1[x]+=w[x];
}
int main()
{
    memset(dp1,127,sizeof(dp1));
    memset(dp2,127,sizeof(dp2));
    memset(dp3,127,sizeof(dp3));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int cur,K,num,son;
        scanf("%d%d%d",&cur,&K,&num);
        w[cur]=K;
        while(num--){scanf("%d",&son);add_edge(cur,son);add_edge(son,cur);}
    }
    dp(1,0);
    printf("%lld\n",min(dp1[1],dp2[1]));
    return 0;
}       

/* z.s */
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=1505;
int n;
vector<int> q[maxn];
int w[maxn];
int f1[maxn],f2[maxn],f3[maxn];
int f[maxn];
int ans;
void dfs(int rt)
{
int cnt=0x7f7f7f7f;
for(int i=0;i<q[rt].size();i++)
{
int tmp=q[rt][i];
dfs(tmp);
f1[rt]+=min(f1[tmp],min(f2[tmp],f3[tmp]));
f2[rt]+=min(f1[tmp],f2[tmp]);
cnt=min(cnt,f1[tmp]-min(f1[tmp],f2[tmp]));
f3[rt]+=min(f1[tmp],f2[tmp]);
}
f2[rt]+=cnt;
f1[rt]+=w[rt];
}
int main()
{
scanf("%d",&n);
for(int i=1,id,m;i<=n;i++)
{
scanf("%d",&id);
scanf("%d%d",&w[id],&m);
for(int j=1,r;j<=m;j++)
{
scanf("%d",&r);
q[id].push_back(r);
f[r]=id;
}
}
for(int i=1;i<=n;i++)
if(!f[i])
{
dfs(i);
ans=min(f1[i],f2[i]);
break;
}
printf("%d\n",ans);
return 0;
}

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int n_r=1500,oo_max=0x3f3f3f3f,oo_min=0xcfcfcfcf;

struct v_1
{
    int h,v;
    vector<int> s;
}a[n_r+1];

int n,t_h;
int f[n_r+1][3];
bool b[n_r+1];

void work_1(int now)
{
    int v_0=0,v_1=0,v_2=0,min_x_1=oo_max;
    for (int i=1;i<a[now].s.size();i++)
    {
        work_1(a[now].s[i]);
        min_x_1=min(min_x_1,f[a[now].s[i]][2]-f[a[now].s[i]][1]);
        v_0+=min(f[a[now].s[i]][1],f[a[now].s[i]][2]);
        v_1+=min(f[a[now].s[i]][1],f[a[now].s[i]][2]);
        v_2+=min(f[a[now].s[i]][0],min(f[a[now].s[i]][1],f[a[now].s[i]][2]));
    }
    v_1+=(min_x_1>0)?min_x_1:0;
    v_2+=a[now].v;
    f[now][0]=min(f[now][0],v_0);
    f[now][1]=min(f[now][1],v_1);
    f[now][2]=min(f[now][2],v_2);
}

int main()
{
    while (~scanf("%d",&n))
    {
        memset(b,0,sizeof(b));
        for (int i=1;i<=n;i++)
        {
            int now,m;
            scanf("%d",&now);
            scanf("%d",&a[now].v);
            scanf("%d",&m);
            a[now].s.resize(m+1,0);
            for (int j=1;j<=m;j++)
            {
                scanf("%d",&a[now].s[j]);
                b[a[now].s[j]]=1;
            }
        }
        for (int i=1;i<=n;i++)
            if (b[i]==0)
            {
                t_h=i;
                break;
            }
        memset(f,oo_max,sizeof(f));
        work_1(t_h);
        printf("%d\n",min(f[t_h][1],f[t_h][2]));
    }
}

我的题解+代码

补充：
f[0][0][0]=f[0][0][1]=0;
f[0][1][0]=f[0][1][1]=INF;

#include <cstdio>
#include <algorithm>
const int size=1505;
int n,m,x,i,j;
int son[size][size];
int tot[size],cost[size],flag[size];
int f[size][3];//0表示未被自己或儿子覆盖 1表示自己覆盖 2表示被儿子覆盖
using namespace std;
void init()
{
//freopen("palace.in","r",stdin);
//freopen("palace.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++)
f[i][1]=f[i][2]=1431655;
for (i=1;i<=n;i++)
{
scanf("%d",&x);
scanf("%d%d",&cost[x],&m);
for (j=1;j<=m;j++)
{
int p=++tot[x];
scanf("%d",&son[x][p]);
flag[son[x][p]]=1;//标识为1
}
}
}
void DP(int k)
{
f[k][1]=cost[k];
if (tot[k]==0) return;
for (int i=1;i<=tot[k];i++)
DP(son[k][i]);//往下枚举

//用儿子更新自己的值
for (int i=1;i<=tot[k];i++)
{
int temp=son[k][i];
f[k][1]+=min(f[temp][0],min(f[temp][1],f[temp][2]));
}//自己覆盖,儿子随便怎么样都可以

for (int i=1;i<=tot[k];i++)
{
int s=f[son[k][i]][1]; //自己覆盖的儿子的代价
for (int j=1;j<=tot[k];j++)
if (j!=i)
{
int temp=son[k][j];
s+=min(f[temp][1],f[temp][2]);
}
f[k][2]=min(f[k][2],s);
}//有一个儿子自己覆盖,其他随意(2/1),选一个最优值

for (int i=1;i<=tot[k];i++)
f[k][0]+=f[son[k][i]][2];//自己的儿子被孙子覆盖,但自己未被覆盖
}
int main()
{
init();
for (i=1;i<=n;i++)
if (flag[i]==0) //如果标识为0,就是树根
{
DP(i);
printf("%d\n",min(f[i][1],f[i][2]));
break;
}
return 0;
}

其实我写这道题的时候还不怎么了解<树形DP>,思路不很明朗,wrong answer了很多次……
###QAQ

###不过那些0s的是咋搞的？
记录信息
评测状态 Accepted
题目 P1144 小胖守皇宫
递交时间 2015-10-07 11:54:53
代码语言 C++
评测机 VijosEx
消耗时间 24 ms
消耗内存 636 KiB
评测时间 2015-10-07 11:54:54
评测结果
编译成功

测试数据 #0: Accepted, time = 1 ms, mem = 576 KiB, score = 14
测试数据 #1: Accepted, time = 1 ms, mem = 576 KiB, score = 14
测试数据 #2: Accepted, time = 1 ms, mem = 576 KiB, score = 14
测试数据 #3: Accepted, time = 1 ms, mem = 636 KiB, score = 14
测试数据 #4: Accepted, time = 8 ms, mem = 580 KiB, score = 14
测试数据 #5: Accepted, time = 6 ms, mem = 580 KiB, score = 14
测试数据 #6: Accepted, time = 6 ms, mem = 576 KiB, score = 14
Accepted, time = 24 ms, mem = 636 KiB, score = 98

###代码
#include <iostream>
#include <stdio.h>
using namespace std;
const int inf=2100000000;
int fir[1510];
int nxt[3020];
int link[3020];
int dp[1510][3];
/*dp[now][0]表示now点不安置守卫的最低花费，而是通过其子节点的守卫守卫,dp[now][1]表示now点安置守卫的最低花费,dp[now][2]表示now点不安置守卫，而是通过其父节点的守卫守卫的最低花费*/
int cost[1510]; //每个点的花费
int cnt;
void Link(int a,int b){nxt[++cnt]=fir[a];link[cnt]=b;fir[a]=cnt;}
void search(int now,int pre)
{
dp[now][1]=cost[now];
dp[now][2]=0;
int flag=inf;
for(int i=fir[now];i;i=nxt[i])
{
if(link[i]!=pre){
search(link[i],now);//先向下走，再从下往上DP

dp[now][0]+=min(dp[link[i]][1],dp[link[i]][0]);
dp[now][1]+=min(dp[link[i]][1],min(dp[link[i]][2],dp[link[i]][0]));
dp[now][2]+=min(dp[link[i]][0],dp[link[i]][1]);

//DP

if(dp[link[i]][1]<=dp[link[i]][0])flag=0;
if(flag&&dp[link[i]][1]-dp[link[i]][0]<flag){
flag=dp[link[i]][1]-dp[link[i]][0];
}
//特判，由于dp[now][0]只需要其某一个‘now的子节点’有守卫即可，需特殊处理
}
}

dp[now][0]+=flag; //当now没有子节点时，dp[now][0]=inf;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int a,b,k;
scanf("%d",&a);
scanf("%d",&cost[a]);
scanf("%d",&k);
while(k--){
scanf("%d",&b);
Link(a,b);
Link(b,a);
}
}
search(1,0);
printf("%d",min(dp[1][0],dp[1][1]));
}

var son:array[0..1500,0..1500] of longint;
a:array[0..1500,0..2] of longint;
w,fa:array[0..1500] of longint;
n,m,i,j,k,l:longint;
function min(x,y,z:longint):longint;
begin
if x<=y then
if x<=z then exit(x);
if y<=x then
if y<=z then exit(y);
if z<=x then
if z<=y then exit(z);
end;
procedure dp(i:longint);
var r,o,l,m:longint;
begin
if son[i,0]=0 then begin a[i,1]:=w[i]; a[i,0]:=w[i]; exit; end;
for r:=1 to son[i,0] do
dp(son[i,r]);
a[i,1]:=w[i];
for r:=1 to son[i,0] do
a[i,1]:=a[i,1]+min(a[son[i,r],0],a[son[i,r],1],a[son[i,r],2]);
for r:=1 to son[i,0] do
a[i,2]:=a[i,2]+min(a[son[i,r],0],a[son[i,r],1],maxlongint);
m:=0; l:=maxlongint;
for r:=1 to son[i,0] do
if a[son[i,r],1]-a[son[i,r],0]<l then
begin
l:=a[son[i,r],1]-a[son[i,r],0];
m:=son[i,r];
end;
for r:=1 to son[i,0] do
if son[i,r]<>m then
a[i,0]:=a[i,0]+min(a[son[i,r],1],a[son[i,r],0],maxlongint)
else
a[i,0]:=a[i,0]+a[son[i,r],1];
end;
begin
read(n);
for i:=1 to n do
begin
read(j,w[j],m); son[j,0]:=m;
for l:=1 to m do
begin
read(son[j,l]);
fa[son[j,l]]:=j;
end;
end;
j:=1;
while fa[j]<>0 do
j:=fa[j];
dp(j);
writeln(min(maxlongint,a[j,0],a[j,1]));

end.
我想说DP思维都是很重要的，一开始错了，就难做了。

记录信息
评测状态 Accepted
题目 P1144 小胖守皇宫
递交时间 2015-08-15 20:06:13
代码语言 Pascal
评测机 VijosEx
消耗时间 0 ms
消耗内存 840 KiB
评测时间 2015-08-15 20:06:13
评测结果
编译成功

Free Pascal Compiler version 2.6.4 [2014/03/06] for i386
Copyright (c) 1993-2014 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
Linking foo.exe
120 lines compiled, 0.1 sec , 29456 bytes code, 1628 bytes data
测试数据 #0: Accepted, time = 0 ms, mem = 800 KiB, score = 14
测试数据 #1: Accepted, time = 0 ms, mem = 800 KiB, score = 14
测试数据 #2: Accepted, time = 0 ms, mem = 796 KiB, score = 14
测试数据 #3: Accepted, time = 0 ms, mem = 840 KiB, score = 14
测试数据 #4: Accepted, time = 0 ms, mem = 796 KiB, score = 14
测试数据 #5: Accepted, time = 0 ms, mem = 796 KiB, score = 14
测试数据 #6: Accepted, time = 0 ms, mem = 796 KiB, score = 14
Accepted, time = 0 ms, mem = 840 KiB, score = 98
代码
program P1144;
type
tNode=record
num:integer;
first,last:integer;
cost:integer;
end;

var
size:integer;
child:array[1..1500] of integer;
node:array[1..1500] of tNode;
loc:array[1..1500] of integer;
answer:array[1..1500,0..2] of longint;
i,j,k,top,temp:integer;
function getRoot:integer;
var
i:integer;
flag:array[1..1500] of boolean;
begin
for i:=1 to top do
begin
flag[i]:=true;
end;
for i:=1 to top do
begin
flag[child[i]]:=false;
end;
for i:=1 to top do
begin
if flag[i] then
begin
exit(loc[i]);
end;
end;
end;
function min(a,b:longint):longint;
begin
if a<b then
begin
exit(a);
end;
exit(b);
end;

function dp(this,flag:integer):longint;
var
i:integer;
sum:longint;
begin
if answer[this,flag]>=0 then
begin
exit(answer[this,flag]);
end;
if node[this].last<node[this].first then
begin
if flag<>0 then
begin
answer[this,flag]:=node[this].cost;
end
else
begin
answer[this,flag]:=0;
end;
exit(answer[this,flag]);
end;
sum:=0;
for i:=node[this].first to node[this].last do
begin
sum:=sum+dp(loc[child[i]],0);
end;
dp:=sum+node[this].cost;
if flag<>2 then
begin
sum:=0;
for i:=node[this].first to node[this].last do
begin
sum:=sum+dp(loc[child[i]],1);
end;
for i:=node[this].first to node[this].last do
begin
dp:=min(dp,sum-dp(loc[child[i]],1)+dp(loc[child[i]],2));
end;
end;
if flag=0 then
begin
sum:=0;
for i:=node[this].first to node[this].last do
begin
sum:=sum+dp(loc[child[i]],1);
end;
dp:=min(dp,sum);
end;
answer[this,flag]:=dp;
end;
begin
top:=1;
readln(size);
for i:=1 to size do
begin
read(j);
loc[j]:=i;
node[i].num:=j;
read(node[i].cost,j);
node[i].first:=top;
node[i].last:=top+j-1;
for k:=top to top+j-1 do
begin
read(temp);
child[k]:=temp;
end;
top:=top+j;
end;
for i:=1 to size do
begin
answer[i,0]:=-1;
answer[i,1]:=-1;
answer[i,2]:=-1;
end;
writeln(DP(getRoot,1));
end.

另answer[i,0]表示i号节点被他爸罩着，这个子树的最少花费，answer[i,1]表示第i个节点不被他爸罩着，他爸也不要求他罩的最少花费。answer[i,2]表示这个节点需要罩着他爸的最小花费。那么

answer[i,0]=求和(answer[i的子树，1])
answer[i,1]=min(求和(answer[i的大部分子树,0])+answer[i剩下一个子树,2],求和(answer[i的子树,0])+cost[i]);
answer[i,2]=cost[i]+求和(answer[i的子树,0])

树形DP
dp(x,flag,flag)表示标号为x的节点是否选，而且他是否被父亲或自己看住。
dp(x,1,1)=Σmin(dp(ch[x][i],1,1),dp(ch[x][i],0,1));
dp(x,0,1)=Σmin(dp(ch[x][i],1,1),dp(ch[x][i],0,0));
dp(x,0,0)的转移复杂一点：从儿子中找出dp(ch[x][i],0,0)-dp(ch[x][t],1,1)最大的点，选中他来看住父亲，
dp(x,0,0)=dp(ch[x][t],1,1)+Σmin(dp(ch[x][i],0,0),dp(ch[x][i],1,1))(i!=t);（在此种情况下某种节点没有孩子，便返回INF）