题目大意
对一个二叉树的节点进行红、绿、蓝的染色,父子节点、兄弟节点之间不同色。求最多/少能染多少个绿色节点。
二叉树的给出方式为一个只由 0、1、2 组成的数字序列。若为 0 ,表示叶子节点;若为 1,表示有一个子节点,之后的序列描述这个节点的子树;若为 2,表示有两个子节点,之后的序列描述子树。
1⩽n⩽500,000
题目链接
【ZJOI 2006】三色二叉树 - Luogu 2585
题解
树形 DP。
不用管不是绿色的节点是红色还是蓝色。
记 f[u,0/1] 表示节点 u 在不是/是绿色时子树的答案,转移为(以最大值为例):
\begin{align}
f[u, \; 1] &= f[u.lc, \; 0] + f[u.rc, \; 0] + 1 \\
f[u, \; 0] &= max(f[u.lc, \; 0] + f[u.rc, \; 1], \; f[u.lc, \; 1] + f[u.rc, \; 0])
\end{align}
最小值同理。
代码
节点和边根本不记录多少东西,就不用结构体了。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| #include <cstdio> #include <cstring> #include <algorithm> const int MAXN = 500005; int f[MAXN][2]; int l[MAXN], r[MAXN]; void readTree(int u = 1) { static int nodeIndex = 1; char ch = getchar(); if (ch == '0') return; l[u] = ++nodeIndex; readTree(nodeIndex); if (ch == '2') { r[u] = ++nodeIndex; readTree(nodeIndex); } } void dpMax(int u = 1) { if (u == 0) return; dpMax(l[u]); dpMax(r[u]); f[u][1] = f[l[u]][0] + f[r[u]][0] + 1; f[u][0] = std::max(f[l[u]][1] + f[r[u]][0], f[l[u]][0] + f[r[u]][1]); } void dpMin(int u = 1) { if (u == 0) return; dpMin(l[u]); dpMin(r[u]); f[u][1] = f[l[u]][0] + f[r[u]][0] + 1; f[u][0] = std::min(f[l[u]][1] + f[r[u]][0], f[l[u]][0] + f[r[u]][1]); } int main() { readTree(); dpMax(); int ansMax = std::max(f[1][1], f[1][0]); memset(f, 0, sizeof (f)); dpMin(); int ansMin = std::min(f[1][1], f[1][0]); printf("%d %d\n", ansMax, ansMin); return 0; }
|