三色二叉树 解题报告
问题描述
一棵二叉树可以按照如下规则表示成一个由0、1、2组成的字符序列，我们称之为「二叉树序列S」。
例如，下图所表示的二叉树可以用二叉树序列S=21200110来表示。
你的任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。
给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。
输入文件
输入文件名：TRO.IN
输入文件仅有一行，不超过10000个字符，表示一个二叉树序列。
输出文件
输出文件名：TRO.OUT
输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。
样例输入 1122002010
样例输出 5 2
思路分析
简单的树形动态规划。这三种颜色是平级的。所谓多少个点能够被染成绿色，其实染成什么色都一样。
对于一颗树，分为两种情况考虑：
- 父亲染成绿色，则数量为两个子树不染成绿色的数量之和＋1。
- 父亲不染成绿色，则数量为两个子树一个染成绿色，另一个不染成绿色的数量之和的最大值或最小值。
这个题目的建树过程也需要注意。
完整代码
//By Ceeji
//Date: 2009-3-12
//HAOI test 2 - Problem 2
//Type: Tree DP
//State: Accepted
Program tro;
Type node=record
l,r:longint;
end;
Var str:ansistring;
ch:char;
i,j,k,len,n,key,nn:longint;
a:array[1..30000]of node; // tree
dp:array[1..30000,1..4]of longint; //1: has green 2:not has green
b:array[1..30000]of boolean;
Function max(i,j:longint):longint;
begin
if i>j then exit(i) else exit(j);
end;
Function min(i,j:longint):longint;
begin
if i<j then exit(i) else exit(j);
end;
Procedure maketree(j:longint);
var c:char;
begin
c:=str[n];
if c='0' then
begin
exit;
end;
if c='1' then
begin
inc(n);
a[j].l:=n;
a[j].r:=0;
maketree(n);
exit;
end;
if c='2' then
begin
inc(n);
a[j].l:=n;
maketree(n);
inc(n);
a[j].r:=n;
maketree(n);
end;
end;
Procedure work(i:longint);
begin
if b[i] then exit;
b[i]:=true;
if a[i].l=0 then begin dp[i,1]:=0; dp[i,2]:=1; dp[i,3]:=0; dp[i,4]:=1; exit; end
else begin
work(a[i].l);
if a[i].r<>0 then work(a[i].r);
dp[i,1]:=max(dp[a[i].l,2]+dp[a[i].r,1],dp[a[i].l,1]+dp[a[i].r,2]);
dp[i,2]:=dp[a[i].l,1]+dp[a[i].r,1]+1;
dp[i,3]:=min(dp[a[i].l,3]+dp[a[i].r,4],dp[a[i].l,4]+dp[a[i].r,3]);
dp[i,4]:=dp[a[i].l,3]+dp[a[i].r,3]+1;
end;
end;
begin
assign(input,'tro.in'); reset(input);
assign(output,'tro.out'); rewrite(output);
readln(str);
fillchar(a,sizeof(a),0);
fillchar(dp,sizeof(dp),0);
len:=length(str);
n:=1; key:=1;
maketree(1);
str:='';
work(1);
writeln(max(dp[1,1],dp[1,2]),' ',min(dp[1,3],dp[1,4]));
close(output);
end.
题外话：我帮你整理了包括 AI 写作、绘画、视频（自媒体制作）零门槛 AI 课程 + 国内可直接顺畅使用的软件。想让自己快速用上 AI 工具来降本增效，辅助工作和生活？限时报名。
© 转载需附带本文链接，依据 CC BY-NC-SA 4.0 发布。