洛谷P2585 [ZJOI2006]三色二叉树 题解

题目链接：P2585 [ZJOI2006]三色二叉树

题意：

一棵二叉树可以按照如下规则表示成一个由 \(0\)、\(1\)、\(2\) 组成的字符序列，我们称之为“二叉树序列 \(S\)”：

\[S= \begin{cases} 0& \text表示该树没有子节点\\ 1S_1& 表示该树有一个节点，S_1 为其子树的二叉树序列\\ 2S_1S_2& 表示该树由两个子节点，S_1 和 S_2 分别表示其两个子树的二叉树序列 \end{cases}\]

例如，下图所表示的二叉树可以用二叉树序列 \(S=\texttt{21200110}\) 来表示。

你的任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不同。给定一颗二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。

对于全部的测试点，保证 \(1 \leq |s| \leq 5 \times 10^5\)，\(s\) 中只含字符 0 1 2。

入门级的树形dp

设 \(f_i\) 表示染 \(i\) 所在子树，\(i\) 染绿色的最大/最小绿色结点数，

\(g_i\) 表示染 \(i\) 所在子树，\(i\) 不染绿色的最大/最小绿色结点数。 \[ f_i = g_l+g_r+1 \\g_i = \max/\min\left\{f_l+g_r,~g_l+f_l\right\} \] 跑个dfs建树即可

时间复杂度 \(O(n)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(5e5+15)

char s[N];
int n,rt,f[N],g[N],ch[N][2],cnt;
void build(int &u)
{
    u=++cnt;
    int c=s[u]-'0';
    if(c==0)return;
    if(c==1)build(ch[u][0]);
    if(c==2)build(ch[u][0]),build(ch[u][1]);
}
#define ls(x) (ch[x][0])
#define rs(x) (ch[x][1])
void solve(int ck)
{
    for(int i=n; i>=1; i--)
    {
        f[i]=g[ls(i)]+g[rs(i)]+1;
        if(!ck)g[i]=max(f[ls(i)]+g[rs(i)],g[ls(i)]+f[rs(i)]);
        else g[i]=min(f[ls(i)]+g[rs(i)],g[ls(i)]+f[rs(i)]);
    }
    if(!ck)cout << max(f[1],g[1]) << ' ';
    else cout << min(f[1],g[1]) << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> (s+1); n=strlen(s+1); build(rt);
    solve(0); solve(1);
    return 0;
}

转载请说明出处