#2330. 「清华集训 2017」榕树之心

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: samzhang

题目描述

深秋。冷风吹散了最后一丝夏日的暑气,也吹落了榕树脚下灌木丛的叶子。相识数年的 Evan 和 Lyra 再次回到了小时候见面的茂盛榕树之下。小溪依旧,石桥依旧,榕树虽是历经荣枯更迭,依旧亭亭如盖,只是 Evan 和 Lyra 再也不是七八年前不经世事的少年了。
……
“已经快是严冬了,榕树的叶子还没落呢……”
“榕树是常绿树,是看不到明显的落叶季节的……”
“唉……想不到已经七年了呢。榕树还是当年的榕树,你却不是当年的你了……”
“其实又有什么是一成不变的呢,榕树常绿,翠绿树冠的宏观永恒,是由无数细小树叶的荣枯更迭组成的。在时间的流逝中一切都在不断变化着呢……”
“但你看这榕树,日日如此,季季如此,年年如此,仿佛亘古不变般,盘根错节,郁郁葱葱。我在想,或许成为一棵树更好吧,任时间从枝叶间流过,我只守这一片绿荫就好。”
“榕树固然长久,但在这无限的时光里,终归是要湮灭于尘土的。与其像榕树一般,植根于一方泥土中感受年复一年的四季更替。倒不如在有限的时间里看过尽可能多的世界吧。再说了,榕树虽生长缓慢,却依旧会在每年春天抽出一根新的枝条去向外探索的呢……”
“真的吗,榕树在她漫长的一生里,就是这样往外一步步探索的吗?”
“毕竟就算树冠看起来一成不变,榕树也会随着时间周期变化,春天到了自然就是生长的时候了,她也应当做出对应的表现吧……”
“相比于对季节更替做出本能的生长,我倒宁愿相信,榕树有一颗活跃的的,探索的心。”
“其实榕树是有心的,榕树刚刚种下的时候,心就在根的地方发芽了。以后每年春天榕树长出新枝条的时候,心就会向着新枝条的方向移动一点,这样就能更靠近外面的世界了。你看这头顶上的枝条,纵横交错,其实心已经在这枝杈间,移动了数十载了呢……”
“哇,也就是说,这密密麻麻的树杈中的某个地方,藏着这棵榕树的心吗?”
“没错,可是要知道它在哪,就得另花一番功夫了……”
“呀,这时候想想,一株树还是不如一个人好……比如你,要是这样贴上去的话,就能听到跳动的声音呢……”
……

一棵榕树可以抽象成一棵 n 个结点的有根树,其中结点编号为 1 \sim n ,而 1 号点就是根节点。初始时,树只有 1 号点,而心也在 1 号点。之后每一步,树都会长出一个新结点,即某个和当前已经存在的某个结点相邻的结点被加入了树中,之后,心会沿着心到新加结点的简单路径移动一步。这棵 n 个结点的树有很多种生长的顺序,不同的顺序可能会导致最终心的位置不同。现在,Evan 和 Lyra 想知道,哪些结点可能是心在生长过程结束时停留的位置呢?

例如一棵大小为 4 的树,连边为 \{<1,2>,<1,3>,<1,4>\} ,我们有三种不同的生长顺序可以让心分别停留在 2,3,4 号节点上:

最终停留在 2 号点:

  1. 1 生长出 3 ,心从 1 移动到 3 ,
  2. 1 生长出 4 ,心从 3 移动回 1 ,
  3. 1 生长出 2 ,心从 1 移动到 2 .

最终停留在 3 号点:

  1. 1 生长出 2 ,心从 1 移动到 2 ,
  2. 1 生长出 4 ,心从 2 移动回 1 ,
  3. 1 生长出 3 ,心从 1 移动到 3 .

最终停留在 4 号点:

  1. 1 生长出 2 ,心从 1 移动到 2 ,
  2. 1 生长出 3 ,心从 2 移动回 1 ,
  3. 1 生长出 4 ,心从 1 移动到 4 .

而我们可以证明,不存在任何一种可能的生长顺序使得心停留在 1 号点。

输入格式

从标准输入读入数据。

输入第一行一个两个正整数 W, T ,分别表示子任务编号(在样例中 W=0 )和数据组数,接下来是 T 组数据的描述,对于每组数据:

第一行一个正整数 n 表示树上结点的个数。

接下来 n-1 行,每行两个正整数 a_i,b_i ,表示编号 a_i,b_i 的结点间有一条树边,保证 a_i \neq b_i 并且输入的 n-1 条边恰好构成了一棵树。

输出格式

输出到标准输出。

若输入的 W 不等于 3 ,对于每组数据输出一行一个长度为 n 01 字符串,表示编号为 1 \sim n 的结点是否有可能是心最后所在的位置,若 01 字符串对应位是 1 则表示可能,为 0 则表示不可能。

若输入的 W 等于 3 ,则对每组数据输出一个字符表示 1 号点的答案。

样例

样例输入 1

0 3
4
1 2
1 3
1 4
6
1 2
1 3
1 4
4 5
5 6
10
1 2
1 3
3 4
3 5
3 6
4 7
7 8
8 9
9 10

样例输出 1

0111
000101
0000001010

样例 2

见附加文件下的 ex_2.inex_2.ans

数据范围与提示

Subtask 1[10pts]

T \leq 50; n \leq 15

Subtask 2[10pts]

T \leq 20; n \leq 10^5 。 除了 1 号点之外,每个点度数(包括父亲)不超过 2

Subtask 3[10pts]

T \leq 200; n \leq 100 。 只输出一个字符表示 1 号点答案,即保证 1 号点答案正确即可。

Subtask 4[35pts]

T \leq 20; n \leq 10^3

Subtask 5[35pts]

T \leq 20; n \leq 10^5