subject

The main idea of the topic

Give you a tree, each node has three kinds of black, white and gray colors.
You have to cut off some edges (each edge needs to pay a certain price) so that every tree in the forest can meet the following requirements:
No black dots or at most one white dot.

Thinking process

This problem is a tree DP...
For each subtree, there are \ (5 \) states:

1. Status \ (00 \), indicating no black and white dots.
2. Status \ (01 \), indicating that there is no black dot, only one white dot.
3. Status \ (02 \), indicating that there are no black dots, and there are two or more white dots.
4. Status \ (10 \), indicating that there is a black dot and no white dot.
5. Status \ (11 \), indicating that there is a black dot and a white dot.

And then there's the long equation of state transition...
Give it in after typing, 10 points...
Turn to autistic mode, only to find that the original state \ (02 \) only has two white dots...

Positive solution

My approach is also one of the solutions.
The method of problem solving is relatively powerful, with only three states:

1. \(F(v) \) means there are no black dots, and any number of white dots.
2. \(G(v) \) means there are any number of black dots, but no white dots.
3. \(H(v) \) indicates that there are any number of black dots and a white dot.

Then transfer...

Code

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;
}

summary

The most important thing about DP is to be careful...