牛客NOIP暑期七天营-普及组5-B小混沌的RYB树

题目大意：一棵树，相邻两点不能同色，现有红黄蓝以及各点涂各种颜色的价值，请问涂色后最大价值是多少？

f[i][j]表示结点i涂颜色j子树的最大价值。如果i点图j色，那么儿子结点只能图另外2中颜色，取最大值即可。

最终答案是f[1][0]、f[1][1]、f[1][2]里面找。

#include <bits/stdc++.h>
#define LL long long
#define N 100005
using namespace std;
LL n, m, i, j, k, a, b, ans;
LL h[N], v[N][3], f[N][3], u[N];
struct AB{
    LL a, b, n;
} d[N*2];
void cun(LL a, LL b){
    d[++k].a = a, d[k].b = b;
    d[k].n = h[a], h[a] = k;
}
void dfs(LL a, LL p){
    LL b, c, i, j, k;
    if(u[a]) return;
    u[a] = 1;//已经搜过，已知该点涂色的信息
    for(c=0; c<3; c++){
        f[a][c] = v[a][c];
        for(i=h[a]; i; i=d[i].n){
            b = d[i].b;
            if(b != p){//是儿子
                dfs(b, a);//处理好儿子的信息
                for(j=k=0; j<3; j++){//枚举儿子的颜色
                    if(j == c) continue;
                    k = max(k, f[b][j]);
                }
                f[a][c] += k;
            }
        }
    }
}
int main(){
    scanf("%lld", &n);
    for(i=1; i<n; i++){
        scanf("%lld%lld", &a, &b);
        cun(a, b);
        cun(b, a);
    }
    for(i=1; i<=n; i++){
        for(j=0; j<3; j++){
            scanf("%lld", &v[i][j]);
        }
    }
    dfs(1, 0);
    ans = max(f[1][0], max(f[1][1], f[1][2]));
    printf("%lld\n", ans);
    return 0;
}