Alice 是一个身怀改变世界的抱负的著名企业家,手中掌控很多著名的公司,为了更好的管理, Alice
建立了一套很完善的架构体系,已知 Alice 的企业的架构体系是一棵树,每个节点代表一个人。对于每
个节点,它的父节点就是这个人的直接 leader,每个节点都有一个权值,代表这个人的爱好,每对属于
同一直接 leader 的节点如果有相同的爱好那么他们就会给公司产生1的和谐度,如果一个人和他/她的直
接 leader 的爱好相同也会给公司产生1的和谐度,但是再完美的公司都会产生离职的情况,如果一个人
离职,并且这个人有直接下属,就从这个人的直接下属中选一个成为这个部门新的 leader,使得新的组
织架构的和谐度最高,新晋的人汇报给离职的人的 leader(如果存在的话),同时新 leader 的原来下属
的直接 leader 不变, Alice 想知道如果某个人离职整个公司的和谐度是多少。
Input
第一行两个正整数 n, m 分别代表公司的总人数和爱好的种数。
第二行有 n 个整数,第 i 个数 a i ,代表第 i 个人的爱好。
后面 n − 1 行每行两个数u,v代表 u,v 存在上下属关系(上下级关系不确定)。
假设树根为 1,即 1 号员工是公司的ceo,他/她不需要汇报给任何人。
1 ≤ m ≤ n ≤ 100, 000
1 ≤ a i ≤ m
Output
输出一行n个数,第i个数代表如果编号为 i 的人离职,公司的和谐度会是多少,以空格分隔,行末无空
格。