前景导入

当 \(t\in [1,2]\) 时，本题如何求解？

答：树形dp

设 \(f[i]\) 为以 \(i\) 为根的树，根节点的晶蝶已消散且儿子节点的晶蝶还未被惊动，能获得的最大晶蝶数。

则有状态转移方程 \(f[i]=(\sum f[u])+max(a[u])\) ，其中 \(u\) 为 \(i\) 的儿子。

最终的答案即为 \(f[1]+a[1]\)

划向更深处

当 \(t=3\) 时，特殊点在哪？

我可以在踏入儿子节点后，再返回根节点，然后踏入 \(t=3\) 的节点，这样的决策存在着可能的更大值

设此时踏入的儿子节点为 \(v\) ， \(g[i]\) 为以 \(i\) 为根的树，根节点的晶蝶和儿子节点的晶蝶均已消散，能获得的最大晶蝶数。

则可能的更大值为
\(f[i]=(\sum f[u])-f[v]+g[v]+a[v]+maxs\)
，其中 \(i_{maxs} \neq v\) 且 \(maxs\) 为所有 \(t=3\) 的节点中最大的 \(a\)

\(Code\)

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

vector<ll> E[100005];
ll g[100005];
ll f[100005];
ll t[100005];
ll a[100005];

inline void read(ll &x) {
    x = 0;
    ll flag = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-') flag = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    x *= flag;
}

inline void write(ll x) {
    if(x < 0) {
        putchar('-');
        x = -x;
    }
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

void ss(ll now, ll fa) {
    ll max1=0, max1_i, max2=0, max2_i;

    ll add=0;
    for(auto next: E[now]) {
        if(next == fa) continue;

        ss(next, now);

        g[now] += f[next];
        add = max(add, a[next]);

        if(t[next] == 3) {
            if(a[next] > max1) {
                max2 = max1;
                max2_i = max1_i;
                max1 = a[next];
                max1_i = next;
            } else if(a[next] > max2) {
                max2 = a[next];
                max2_i = next;
            }
        }
    }

    f[now] = g[now] + add;

    for(auto next: E[now]) {
        if(next == fa) continue;
        if(next != max1_i) {
            f[now] = max(f[now], g[now] - f[next] + g[next] + a[next] + max1);
        } else {
            f[now] = max(f[now], g[now] - f[next] + g[next] + a[next] + max2);
        }
    }
}

int main() {
    ll N;
    read(N);
    while(N--) {
        ll n;
        read(n);
        for(ll i=1; i<=n; i++) {
            read(a[i]);
            E[i].clear();
            f[i] = 0;
            g[i] = 0;
            t[i] = 0;
        }

        for(ll i=1; i<=n; i++) read(t[i]);

        for(ll i=1; i<n; i++) {
            ll x, y;
            read(x); read(y);

            E[x].push_back(y);
            E[y].push_back(x);
        }

        ss(1, 0);

        write(f[1]+a[1]);
        putchar('\n');
    }
    return 0;
}