题目

题目大意

给你一棵树，每个节点有三种黑、白、灰三种颜色。
你要割掉一些边（每条边被割需要付出一定的代价），使得森林的每棵树满足：
没有黑点或至多一个白点。

思考历程

这题一看就知道是一个树形DP……
对于每棵子树，有\(5\)种状态：

1. 状态\(00\)，表示没有黑点和白点。
2. 状态\(01\)，表示没有黑点，只有一个白点。
3. 状态\(02\)，表示没有黑点，有两个或以上个白点。
4. 状态\(10\)，表示有一个黑点，没有白点。
5. 状态\(11\)，表示有一个黑点，一个白点。

然后就是长长的状态转移方程……
打出来之后交上去，10分……
调到自闭，这才发现，原来状态\(02\)只存了两个白点……

正解

我的做法也是正解之一。
题解的做法比较强大，只有三个状态：

1. \(F(v)\)表示没有黑点，有任意多白点
2. \(G(v)\)表示有任意多黑点，没有白点
3. \(H(v)\)表示有任意多黑点，有一个白点

然后转移即可……

代码

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 300010
int n;
int col[N];
struct EDGE{
    int to,w;
    EDGE *las;
} e[N*2];
int ne;
EDGE *last[N];
inline void link(int u,int v,int w){
    e[ne]={v,w,last[u]};
    last[u]=e+ne++;
}
struct Status{
    long long _00,_01,_02,_10,_11;
} f[N];
long long g[N];
int fa[N];
inline void bfs(){
    static int q[N];
    int head=1,tail=1;
    q[1]=1;
    fa[1]=0;
    while (head<=tail){
        int x=q[head++];
        for (EDGE *ei=last[x];ei;ei=ei->las)
            if (ei->to!=fa[x]){
                fa[ei->to]=x;
                q[++tail]=ei->to;
            }
    }
    memset(f,63,sizeof f);
    for (int i=tail;i>=1;--i){
        int x=q[i];
        if (col[x]==0)
            f[x]._10=0;
        else if (col[x]==1)
            f[x]._01=0;
        else
            f[x]._00=0;
        for (EDGE *ei=last[x];ei;ei=ei->las)
            if (ei->to!=fa[x]){
                int y=ei->to,w=ei->w;
                f[x]._11=min({  f[x]._11+min({f[y]._00,f[y]._10,g[y]+w}),
                                f[x]._10+min(f[y]._01,f[y]._11),
                                f[x]._01+f[y]._10,
                                f[x]._00+f[y]._11});
                f[x]._10=min(   f[x]._10+min({f[y]._00,f[y]._10,g[y]+w}),
                                f[x]._00+f[y]._10);
                f[x]._02=min({  f[x]._02+min({f[y]._00,f[y]._01,f[y]._02,g[y]+w}),
                                f[x]._01+min(f[y]._01,f[y]._02),
                                f[x]._00+f[y]._02});
                f[x]._01=min(   f[x]._01+min(f[y]._00,g[y]+w),
                                f[x]._00+f[y]._01);
                f[x]._00=f[x]._00+min(f[y]._00,g[y]+w);
            }
        g[x]=min({f[x]._00,f[x]._01,f[x]._02,f[x]._10,f[x]._11});
    }
}

int main(){
    freopen("in.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while (T--){
        scanf("%d",&n);
        for (int i=1;i<=n;++i)
            scanf("%d",&col[i]);
        memset(last,0,sizeof last);
        ne=0;
        for (int i=1;i<n;++i){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            link(u,v,w),link(v,u,w);
        }
        bfs();
        printf("%lld\n",g[1]);
    }
    return 0;
}

总结

DP这种东西，最重要的是细心啊……

[JZOJ3347] 【NOI2013模拟】树的难题

原文：https://www.cnblogs.com/jz-597/p/11166318.html