笃志以砺，决起而飞

本解题报告的版权归 Ceeji 所有，转载请注明并保留本注释。 问题描述 一棵二叉树可以按照如下规则表示成一个由0、1、2组成的字符序列，我们称之为“二叉树序列S”： 例如，下图所表示的二叉树可以用二叉树序列S=21200110来表示。 你的任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。

输入文件 输入文件名：TRO.IN 输入文件仅有一行，不超过10000个字符，表示一个二叉树序列。

输出文件 输出文件名：TRO.OUT 输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。

样例输入 1122002010

样例输出 5 2 思路分析 本解题报告的版权归 Ceeji 所有，转载请注明并保留本注释。 简单的树形动态规划。这三种颜色是平级的。所谓多少个点能够被染成绿色，其实染成什么色都一样。对于一颗树，分为两种情况考虑：1、父亲染成绿色，则数 量为两个子树不染成绿色的数量之和＋1。2、父亲不染成绿色，则数量为两个子树一个染成绿色，另一个不染成绿色的数量之和的最大值或最小值。 这个题目的建树过程也需要注意。

完整代码

  //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  [...]