洛谷题单指南-树与图上的动态规划-P2585 [ZJOI2006] 三色二叉树

原题链接：https://www.luogu.com.cn/problem/P2585

题意解读：给二叉树节点染色（红、绿、蓝），父子节点不能同色，兄弟节点不能同色，问最多可以有多少绿色，最少可以有多少绿色。

解题思路：

首先，要根据给定的二叉树序列建树，可以看出二叉树序列是按照DFS顺序给出，序列每个元素代表每个节点有几个子节点，

可以通过栈来维护每个节点的父节点，如果父节点子节点数不为0则建立父子关系，将父节点的子节点数减1，直到0则出栈，这样就可以构建一棵二叉树。

    for(int v = 0; v < str.size(); v++)
    {
        if(stk.size())
        {
            int u = stk.top();
            tr[u].push_back(v);
            if(--sz[u] == 0) stk.pop(); //如果u的子节点数减为0，说明u的子树已经构建完成，可以出栈
        }
        sz[v] = str[v] - '0'; //记录当前节点的子节点数
        if(sz[v]) stk.push(v); //如果当前节点还有子节点，则入栈
    }

然后，通过树形DP来求解，

1、状态表示

设f[i][0]表示以i为根的子树且i是绿色的最大绿色节点数，f[i][1]表示以i为根的子树且i是红色的最大绿色节点数，f[i][2]表示以i为根的子树且i是蓝色的最大绿色节点数。

设g[i][0]表示以i为根的子树且i是绿色的最小绿色节点数，g[i][1]表示以i为根的子树且i是红色的最小绿色节点数，g[i][2]表示以i为根的子树且i是蓝色的最小绿色节点数。

2、状态转移
对于节点u，其左子节点为l，右子节点为r

初始值：
f[u][0] = g[u][0] = 1;
f[u][1] =f[u][2] =g[u][1] =g[u][2] =0;

如果u有1个子节点：
f[u][0] =1+max(f[l][1], f[l][2]);
g[u][0] =1+min(g[l][1], g[l][2]);
f[u][1] =max(f[l][0], f[l][2]);
g[u][1] =min(g[l][0], g[l][2]);
f[u][2] =max(f[l][0], f[l][1]);
g[u][2] =min(g[l][0], g[l][1]);

如果u有2个子节点：
f[u][0] =1+max(f[l][1] +f[r][2], f[l][2] +f[r][1]);
g[u][0] =1+min(g[l][1] +g[r][2], g[l][2] +g[r][1]);
f[u][1] =max(f[l][0] +f[r][2], f[l][2] +f[r][0]);
g[u][1] =min(g[l][0] +g[r][2], g[l][2] +g[r][0]);
f[u][2] =max(f[l][0] +f[r][1], f[l][1] +f[r][0]);
g[u][2] =min(g[l][0] +g[r][1], g[l][1] +g[r][0]);

3、答案
最大值：max(max(f[0][0], f[0][1]), f[0][2])
最小值：min(min(g[0][0], g[0][1]), g[0][2])
100分代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 500005;

vector<int> tr[N];
int f[N][3]; // f[i][0]表示以i为根的子树且i是绿色的最大绿色节点数，f[i][1]表示以i为根的子树且i是红色的最大绿色节点数，f[i][2]表示以i为根的子树且i是蓝色的最大绿色节点数
int g[N][3]; // g[i][0]表示以i为根的子树且i是绿色的最小绿色节点数，g[i][1]表示以i为根的子树且i是红色的最小绿色节点数，g[i][2]表示以i为根的子树且i是蓝色的最小绿色节点数
stack<int> stk; // 栈用于存储当前正在构建的子树的根节点
int sz[N]; // sz[i]表示i的子节点数
string str;

void dfs(int u)
{
    f[u][0] = g[u][0] = 1;
    f[u][1] = f[u][2] = g[u][1] = g[u][2] = 0;

    if(tr[u].size() == 0)  return; // 如果没有子节点，直接返回
    int l, r;
    if(tr[u].size() >= 1) 
    {
        l = tr[u][0]; 
        dfs(l); // 如果左子节点存在，递归处理
        f[u][0] = 1 + max(f[l][1], f[l][2]); 
        g[u][0] = 1 + min(g[l][1], g[l][2]); 
        f[u][1] = max(f[l][0], f[l][2]); 
        g[u][1] = min(g[l][0], g[l][2]);
        f[u][2] = max(f[l][0], f[l][1]);
        g[u][2] = min(g[l][0], g[l][1]); 
    }
    if(tr[u].size() >= 2) 
    {
        r = tr[u][1];
        dfs(r); // 如果右子节点存在，递归处理
        f[u][0] = 1 + max(f[l][1] + f[r][2], f[l][2] + f[r][1]); 
        g[u][0] = 1 + min(g[l][1] + g[r][2], g[l][2] + g[r][1]); 
        f[u][1] = max(f[l][0] + f[r][2], f[l][2] + f[r][0]);
        g[u][1] = min(g[l][0] + g[r][2], g[l][2] + g[r][0]); 
        f[u][2] = max(f[l][0] + f[r][1], f[l][1] + f[r][0]); 
        g[u][2] = min(g[l][0] + g[r][1], g[l][1] + g[r][0]); 
    }
 }

int main()
{
    memset(g, 0x3f, sizeof(g)); // 初始化g数组为最大值
    cin >> str;
    for(int v = 0; v < str.size(); v++)
    {
        if(stk.size())
        {
            int u = stk.top();
            tr[u].push_back(v);
            if(--sz[u] == 0) stk.pop(); //如果u的子节点数减为0，说明u的子树已经构建完成，可以出栈
        }
        sz[v] = str[v] - '0'; //记录当前节点的子节点数
        if(sz[v]) stk.push(v); //如果当前节点还有子节点，则入栈
    }

    dfs(0); 
    cout << max(max(f[0][0], f[0][1]), f[0][2]) 
         << " " 
         << min(min(g[0][0], g[0][1]), g[0][2]);
    return 0;
}