Start: Aug, 31, 2026 14:00:00
AI-prompt作业
End: Jan, 07, 2027 23:59:00
Time elapsed:
Time remaining:

黔灵猕猴II 3433

Time Limit:  1 s      Memory Limit:   256 MB
Submission:3     AC:0     Score:10

Description

黔灵山公园的小老费所在的区域可以被看作一颗有 n 个节点的树,小老费可以沿着树边从顶点向叶子前进,此外,小老费可以对任意点施加魔法,使得该点的下一个点不再是其子节点之一,而是树的顶点,换句话说,小老费从施加魔法的点向下走会被传送回顶点。每个节点都有一个行走值 ai(2≤ ai ≤3),这意味着如果小老费在节点他将沿树边走步。对于每个点现在小老费想知道,如果他在该点施加魔法,且沿树边行走时,一定向着隙的方向移动,在经过 11451455036 次移动后,能否走到从顶点到团点最短路径上的每一个点。为了让小老费尽可能的走到每一个点,小老费的好朋友想要帮助他,所以,在小老费选择了某个点之后,小老费的好朋友可以对从顶点到团点最短路径上的所有点团的行走值进行重新排列。对于每个点,请帮助小老费判断,在小老费的好朋友采取最佳策略的情况下,是否存在一种可能,使得小老费可以在经过1 11451455036 次移动后,走到从顶点到晾最短路径上的每一个点。
注意:
■只有终点是才算作走到,途经不算走到;
■小老费的好朋友的每次交换相互独立,不同点的交换不会互相影响。

Input

第一行为两个整数 n ,p (1≤ n ≤5000,1≤ p ≤ n 表示这棵树的点数和顶点。
第二行包含团个整数,第阶数表示隙的行走值 ai (2≤ ai ≤3)。
接下来 n - 1行,每行两个整数 u ,v (1≤ u,v ≤ n 表示 u 和 v 之间有一条直接相连的边。保证输入的是一颗树。

Output

输出一行团个数,第阶数表示当小老费对瓯施加魔法时的答案。如果可以走到每一个点,输出1,否则输出0。

Samples

input
4 1 2 2 3 3 1 2 1 3 2 4
output
1 0 1 1

Hint

样例解释:
■对于1号点,无论走多少步,都会回到自己,所以可以。
■对于2号点,无论小老费的好朋友如何重新排列都无法做到。