给出一个N个节点的无根树，每条边有非负边权，每个节点有三种颜色：黑，白，灰。
一个合法的无根树满足：树中不含有黑色结点或者含有至多一个白色节点。
现在希望你通过割掉几条树边，使得形成的若干树合法，并最小化割去树边权值的和。

Input

第一行一个正整数N，表示树的节点个数。
第二行N个整数Ai，表示i号节点的颜色，0 表示黑色，1表示白色，2表示灰色。
接下来N-1行每行三个整数Xi Yi Zi，表示一条连接Xi和Yi权为Zi的边。

Output

输出一个整数表示其最小代价。

Sample Input

Sample Output

10
样例解释：
花费10的代价删去边(1, 2)和边(2, 5)。

Data Constraint

20%的数据满足N≤10。
另外30%的数据满足N≤100,000，且保证树是一条链。
100%的数据满足N≤300,000，0≤Zi≤1,000,000,000，Ai∈{0,1,2}。

solution

一眼显然树形DP

仔细思考发现不好转移

还是暴力适合我

void add(int x,int y,int z)
{
    ver[++cut] = y; next[cut] = head[x]; head[x] = cut; w[cut] = z;
}
int lowbit(int x)
{
    return x&-x;
}
int count(int x)
{
    int num = 0;
    for(; !(x&1); x >>= 1)num ++;
    return ++num ;
}
void dfs(int x,int fa)
{
    book[x] = 1;
    if(color[x] == 1) white++;
    else if(color[x] == 0) black++;
    for(R int i = head[x]; i; i = next[i])
    {
        int y = ver[i], z = w[i];
        if(y == fa)continue;
        dfs(y,x);
    }
}
bool check()
{
    for(R int i = 1; i <= n; i++)
    {
        if(!book[i])
        {
            black = 0; white = 0;
            dfs(i,0);
            if(black && white > 1)return false;
        }
    }
    return true;
}
signed main()
{
    read(n);
    for(R int i = 1; i <= n; i++) read(color[i]);
    if(n<=10)
    {
        for(R int i = 1; i < n; i++) read(a[i]), read(b[i]), read(c[i]), SUM += c[i];
        for(R int i = 0; i <= (1<<(n-1))-1; i++)
        {
            int now = i, sum = 0;
            cut = 0; memset(head,0,sizeof(head)); 
            while(now)
            {
                int which = count(now );
                add(a[which],b[which],c[which]);
                sum += c[which];
                now -= lowbit(now);
            }
            memset(book,0,sizeof(book));
            if(check()) ans = min(ans,SUM - sum );
        }
        writeln(ans);
        return 0;
    }
    writeln(0);
    return 0;
}

问链就是打挂了

正解貌似从下往上扫

dp[i][0 / 1 / 2] 在i节点，0表示没有黑色，1表示没有白色，2表示有一个白色

先挖坑

——————————————————————————————————————————分割线

copy了zjy的

不过没有弄人工栈只有70points

zjy题解

人工栈。。。再挖个坑

code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<queue>
 7 #include<vector>
 8 #include<stack>
 9 #include<set>
10 #include<deque>
11 #include<map>
12 using namespace std;
13 
14 template <typename T> void read(T &x) {
15     x = 0; int f = 1; char c;
16     for (c = getchar(); c < '0' || c > '9'; c = getchar()) if (c == '-') f = -f;
17     for (; c >= '0' && c <= '9'; c = getchar()) x = 10 * x + c - '0' ;
18     x *= f;
19 }
20 template <typename T> void write(T x){
21     if (x < 0) putchar('-'), x = -x;
22     if (x > 9) write(x / 10);
23     putchar(x % 10 + '0');
24 }
25 template <typename T> void writeln(T x) { write(x); putchar('
'); }
26 template <typename T> void writesn(T x) { write(x); putchar(' '); }
27 
28 #define int long long
29 #define inf 123456789012345678
30 #define next net
31 #define P 1000000007
32 #define N 600020
33 #define mid ((l+r)>>1)
34 #define lson (o<<1)
35 #define rson (o<<1|1)
36 #define R register
37 
38 int n,cut;
39 int color[N ];
40 int next[N ],head[N ],ver[N ],w [N ];
41 int f[N ][3],book[N ];
42 inline void add(int x,int y,int z)
43 {
44     ver[++cut] = y; next[cut] = head[x]; head[x] = cut; w[cut] = z;
45 }
46 inline void dfs(int x)
47 {
48     book[x] = 1;
49     if(color[x] == 0) f[x][0] = inf;
50     else if(color[x] == 1) f[x][1] = inf;
51     int maxx = 0;
52     for(R int i = head[x]; i; i = next[i])
53     {
54         int y = ver[i], z = w[i];
55         if(book[y]) continue;
56         dfs(y);
57         if(color[x] == 0)
58         {
59             f[x][1] += min(f[y][1], min(f[y][0], f[y][2]) + z);
60             maxx = max(maxx, min(f[y][1], min(f[y][0], f[y][2]) + z) - f[y][2]);
61         }
62         else if(color[x] == 1)
63         {
64             f[x][0] += min(f[y][0], min(f[y][1], f[y][2]) + z);
65             f[x][2] += min(f[y][1], min(f[y][0], f[y][2]) + z);
66         }
67         else
68         {
69             f[x][0] += min(f[y][0], min(f[y][1], f[y][2]) + z);
70             f[x][1] += min(f[y][1], min(f[y][0], f[y][2]) + z);
71             maxx = max(maxx, min(f[y][1], min(f[y][0], f[y][2]) + z) - f[y][2]);
72         }
73     }
74     if(color[x] != 1) f[x][2] = f[x][1] - maxx;
75 }
76 signed main()
77 {
78     //freopen("tree2.in","r",stdin);
79     //freopen("tree2.out","w",stdout);
80     read(n);
81     for(R int i = 1; i <= n; i++) read(color[i]);
82     for(R int i = 1, x, y, z; i < n; i++)
83     {
84         read(x); read(y); read(z);
85         add(x, y, z); add(y, x, z);
86     }
87     dfs(1);
88     writeln(min(f[1][0], min(f[1][1], f[1][2])));
89     return 0;
90 }

20200722T1 【NOIP2015模拟10.29A组】三色树 Description Input Output Sample Input Sample Output Data Constraint solution code