[ZJOI2006] 三色二叉树 题解
趣题。
首先我们把题目分成两部分：建树和 dp 求解。
建树：观察发现，字符串中的第 \(i\) 个字符就代表图中的第 \(i\) 个节点。如果 \(S_i = 0\)，直接跳过；如果 \(S_i = 1\)，那么 \(i + 1\) 是 \(i\) 唯一的子节点，在两点之间连边，然后继续递归建树即可。难点在于 \(S_i = 2\) 的情况。不难发现，\(i + 1\) 仍然是 \(i\) 的一个子节点，但我们难以确定 \(i\) 的另一个子节点是什么。这时不妨先把 \(i + 1\) 的子树建完，那么建完之后字符串的下一位就是 \(i\) 的另一个子节点。为了方便，可以维护一个变量表示建树已经进行到了第几个节点（也即字符串的第几位）。
void build(int id)
{
mx = max(mx, id);
if(str[id] == '1')
{
G[id].push_back(id + 1), lson[id] = id + 1;
build(id + 1);
}
else if(str[id] == '2')
{
G[id].push_back(id + 1), lson[id] = id + 1;
build(id + 1);
G[id].push_back(mx + 1), rson[id] = mx + 1;
build(mx + 1); // 另一个子节点
}
else
{
/* 之后这里可以加入 dp 的初始化 */
}
}
dp：先考虑求最大值，最小值可以类推得出。不难想到可以设 \(f(u, 0/1/2)\) 表示 \(u\) 节点分别染成 \(3\) 种颜色时， \(T(u)\) 内最多可以有多少个节点染成绿色，洛谷的题解上似乎也都是这样写的。
然而真的需要这样吗？观察发现：红色和蓝色实际上是地位相同的。注意：说它们地位相同不代表可以把它们看作一种颜色。可以这么理解：如果我有某种染色方法，把这个染色方法中的红色节点全部染成蓝色，蓝色节点全部染成红色，得到一个新的染色方法。不难发现这个新的染色方法也是合法的，并且绿色节点的个数保持不变。所以我们实际上并不需要对每个节点都设 \(3\) 种状态，\(2\) 种状态就够了。
于是，设 \(f(u, 1/0)\) 表示\(u\) 节点分别染成绿色/非绿色时， \(T(u)\) 内最多可以有多少个节点染成绿色。——这里，我们不再区分红蓝色的区别，而认为它们都是非绿色。
那么转移方程为：
\[f(u, 1) = f(lson, 0) + f(rson, 0) + 1 \\ f(u, 0) = \max(f(lson, 1) + f(rson, 0), f(lson, 0) + f(rson, 1)) \]初始化叶子节点 \(u\) 的 \(f(u, 1) = 1\)。答案为 \(\max(f(1, 1), f(1, 0))\)。
代码：
#include<bits/stdc++.h>
using namespace std;
constexpr int MAXN = 5e5 + 10;
int n, mx, lson[MAXN], rson[MAXN], f[MAXN][2], g[MAXN][2];
char str[MAXN];
vector<int> G[MAXN];
void build(int id)
{
mx = max(mx, id);
if(str[id] == '1')
{
G[id].push_back(id + 1), lson[id] = id + 1;
build(id + 1);
}
else if(str[id] == '2')
{
G[id].push_back(id + 1), lson[id] = id + 1;
build(id + 1);
G[id].push_back(mx + 1), rson[id] = mx + 1;
build(mx + 1);
}
else
{
f[id][1] = 1, f[id][0] = 0;
g[id][1] = 1, g[id][0] = 0;
}
}
void dfs(int u)
{
for(int v : G[u]) dfs(v);
int ls = lson[u], rs = rson[u];
f[u][1] = f[ls][0] + f[rs][0] + 1;
f[u][0] = max({f[ls][0] + f[rs][1], f[ls][1] + f[rs][0]});
g[u][1] = g[ls][0] + g[rs][0] + 1;
g[u][0] = min({g[ls][0] + g[rs][1], g[ls][1] + g[rs][0]});
}
int main()
{
cin >> (str + 1);
n = strlen(str + 1);
build(1);
// for(int i = 1; i <= n; i++)
// {
// cerr << i << ": ";
// if(G[i].size() == 0) cerr << "The node is a leaf node";
// else for(auto v : G[i]) cerr << v << ' ';
// cerr << endl;
// }
dfs(1);
cout << max(f[1][1], f[1][0]) << ' ' << min(g[1][1], g[1][0]) << endl;
return 0;
}