#6020. 「from CommonAnts」寻找 LCT

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

题目描述

定义树的重心:一个点是树的重心,当且仅当删去这个点后产生的所有连通块的节点数不超过原树节点数的 \frac 1 2 。也就是说,如果原树有 n 个节点,产生的任意连通块节点数不超过 \lfloor\frac n 2\rfloor

LCT(Link-Cut Tree):一种用于解决动态树问题的数据结构,支持两种操作:删去一条边(cut),加入一条连接两个尚未连通的点的边(link)。

你有一棵 n 个节点的树,现在你要交替进行 k 次 cut 和 k 次 link 操作,可以对任意一条边进行操作。你需要解决的问题是:对于每个节点, k 次操作结束后它是否有可能成为新树的重心。为了重心的唯一性,保证 n 是奇数。

输入格式

第一行两个整数 n , k ,表示树的节点数和操作次数。 第二行到第 n 行,第 i+1 行两个整数 u_i v_i ,表示初始时有一条连接 u_i v_i 的边。

输出格式

输出共 n 行。第 i 行一个整数,0 表示第 i 个节点不可能成为重心,1 表示第 i 个节点可能成为重心。

样例

样例输入

7 2
1 2
1 3
1 4
1 5
5 6
6 7

样例输出

1
1
1
1
1
1
1

样例解释

让 5 成为重心的一种方法:断开 (1,2) ,连接 (5,2) ,断开 (5,2) ,连接 (5,2)
让 6 成为重心的一种方法:断开 (1,2) ,连接 (6,2) ,断开 (1,3) ,连接 (6,3)
让 7 成为重心的一种方法:断开 (1,2) ,连接 (7,2) ,断开 (5,1) ,连接 (7,1)

数据范围与提示

与「JZOJ 5028」跳蚤王国(来源:毛啸)类似。