bzoj#P3974. [WF2013]Up a Tree

[WF2013]Up a Tree

题目描述

Anatoly Cheng McDougal 在许多方面都是一个典型的新生。如果可以,他会尝试将代码剪切和粘贴从而替代从头写一段代码。显然,这种方法会无法避免地给他带来一些问题。例如,当他第一次学习树的先序,中序和后序遍历后,就写下了一段树的先序遍历的代码(如左下角所示),随后,他简单的剪切和粘贴的这段代码,然后将输出语句调整到正确的位置,并将过程(函数)重命名。但是,他忘记重新书写将会在内部被调用的过程(函数)名,从而导致生成了如下有问题的树的先序,中序和后序遍历代码。

void prePrint(TNode t){
    output(t.value);
    if (t.left != null)
    	prePrint(t.left);
    if (t.right != null)
    	prePrint(t.right);
}
void inPrint(TNode t){
    if (t.left != null)
    	prePrint(t.left);
    output(t.value);
    if (t.right != null)
    	prePrint(t.right);
}
void postPrint(TNode t){
    if (t.left != null)
    	prePrint(t.left);
    if (t.right != null)
    	prePrint(t.right);
    output(t.value);
}

译者注:prePrint 先序遍历过程(函数),inPrint 中序遍历过程(函数),postPrint 后序遍历过程(函数),TNode 树结点类型,left 左儿子,right 右儿子,null 空结点,output 输出,void 空类型,if 条件语句标志。

此时,Anatoly 表现得不再像一个新生。他其实就测试了自己的代码!不幸地,当输出的结果不正确时,他又变回了新生样。他紧张起来,随即开始随机地改变三个过程中的调用,希望这能奏效。显然,情况更糟了。

Anatoly 的教授用一个随机的字符树测试了这段代码。当她看到了这段程序的输出之时,她已经正确地猜到了刚才发生的事情。但是,她并不想直接地浏览他的代码,相反地,她决定仅仅通过观察程序的输出,来重构 Anatoly 的代码。为了做到这一点,她正确地做了如下的假设:

  • 输出语句在各个过程(函数)已经在正确的位置。(例如,在中序遍历中,输出语句在两个递归调用中间)。

  • 在涉及到这三个过程(函数)的六次递归调用中,恰好有两个调用为先序遍历(prePrint),恰好两次为中序遍历(inPrint),还有恰好两次为后序遍历(postPrint),虽然有可能在错误的过程(函数)里。

不久教授就觉察到,从他的输出中,重构 Anatoly 的代码和测试数据并非易事,而且结果可能是多元的。你需要帮助他重构出所有可能的 Anatoly 的代码。另外,对于所有这样的重构,请您找到能够产生这种输出的,字典序最小的树(将会在输出中详述)。

输入格式

输入只有一个测试点,各点在三行分别有三个字符串:对于某棵树,Anatoly 的先序,中序和后序遍历的输出(和描述保持相同的顺序)。

每个字符串包含 nn 个大写字母,且无分隔。数据保证有解。

输出格式

对于测试点,输出所有可能的重构,以如下方式排序。

输出中,各个重构分为两部分。第一部分为单独一行描述 Anatoly 的代码:先是两个 Anatoly 的先序遍历中的(递归)调用,随即是中序遍历中的(递归)调用,最后是后序遍历中的(递归)调用。调用用 Pre, InPost 描述,空格隔开。例如,若 Anatoly 的代码正确,那么重构的输出应该是 Pre Pre In In Post Post

第二部分包括三行描述会产生观察到的输出的输入数据。第一行为正确的先序遍历,第二行为正确的中序遍历,第三行为正确的后序遍历。

字典序最小的树拥有字典序最小的先序遍历。如果答案仍然多元,字典序最小的树为这当中拥有字典序最小的中序遍历的树。

HFBIGEDCJA
BIGEDCJFAH
BIGEDCJFAH
Pre Post In Post In Pre
HFBJCDEGIA
BIGEDCJFAH
IGEDCJBAFH

数据规模与约定

对于 100%100\% 的数据,4n264\leq n\leq 26