| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
题意每行都是一颗二叉树。 先跳过C,只看UV。U表示中间结点(unite),V表示叶子结点(town),每行都是前序遍历的形式给出。 U只用于表示树的结构,不用于修路(repair road)。 然后,一些结点前会加上C的标识: 如果C加在V前,这个C没用; 如果C加在U前,它可能修路,也可能毁路,规则如下: ① 如果一个CU结点没有祖先CU结点,那么它是一个修路结点,表示这个U下面的所有叶子两两间都修路。 ② 如一个CU结点的最近祖先CU结点是个修路结点,那么它是一个毁路结点,表示这个U下面被祖先修好的路全部毁掉。 ③ 如一个CU结点的最近祖先CU结点是个毁路结点,那么它是一个修路结点,表示这个U下面被祖先毁掉的路再两两间全部修好。 ④ 初始时,所有的路全部损毁。 最后,求一个含叶子数最多的集合,这个集合内任意两片叶子间都没有路。 下面举几个例子帮助理解: U V U V V // 答案3。没有CU结点,没有路。 C U U V V U V V // 答案1。CU是根结点,叶子两两间都有路。 C U C U V V V // 答案2。左侧CU结点把左侧路全毁了。 C U C U U V V V U V V // 答案3。理由同上。 C U C U C U V V V U V V // 答案2。第三层CU结点又把路修上了。 最后最后,为什么这句话能理解出规则②③,我也不知道…… 我也是倒推好久才给出这个解释的…… ”whenever the workers of a division accepted an order to repair all of the destroyed roads, they also automatically supposed that they can stop maintaing the roads they maintained before, and such roads decayed quickly. ” Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator