寒假营6-J 绝妙的平衡

知识点

贪心，树（图）上dfs

题意

思路

1. 考虑何时无解：红结点没有白儿子的时候（红点是叶子/红点的儿子都是红点）
2. 考虑其余情况的构造：
   1）初始：所有结点都赋值为2；
   2）“后序遍历”整棵树，遇到红结点，检查此时子树结点的和mod 4的余数；
   3）余数为0：好得很；余数为1：红结点本身改为1；余数为2：红结点本事和它的一个白儿子改为1。

注意

1. 题目没有说是二叉树!!!!（存的时候当图来存，不能是lch、rch）；
2. “子树”是包含它自己的。

完整代码

#include<bits/stdc++.h>
#define N 100010
using namespace std;
int n, sum[N], num[N]; //子树的权值的和，该点权值
vector<int> v[N];
string col; //颜色
void dfs(int x) { //搜编号为x的点
    if(v[x].empty()) { //到底了
        if(col[x]=='R') {
            printf("-1"); exit(0); //无解1：红点是叶子
        }
        return; 
    }
    for(auto tmp:v[x]) { //搜儿子结点
        dfs(tmp);
        sum[x]+=sum[tmp];
    }
    if(col[x]=='R') { //遇到红节点，检查sum[x]是否是3的倍数
        bool ok=0;
        if(sum[x]%3==1) num[x]=1; //它本身改为1
        else if(sum[x]%3==2) {
            num[x]=1; //它本身改为1
            for(auto tmp:v[x]) { //它的一个白儿子改为1
                if(col[tmp]=='W') {
                    num[tmp]=1; ok=1; break;
                }
            }
            if(!ok) {
                printf("-1"); exit(0); //无解2：红点的儿子都是红点
            }
        }
        sum[x]=0; //保证了sum[x]是3的倍数 -> 相当于sum[x]=0
    }
    return;
}
int main() {
    scanf("%d", &n);
    cin>>col; col=" "+col;
    for(int i=1;i<=n-1;i++) {
        int x; scanf("%d", &x); //x有儿子i+1
        v[x].push_back(i+1);
    } //建树（图）
    for(int i=1;i<=n;i++) num[i]=2, sum[i]=2; //初始：所有点都赋为2
    dfs(1);
    for(int i=1;i<=n;i++) printf("%d", num[i]);
    return 0;
}