ACMORE
Vjudge
杭电HDUOJ
杭电HDUOJ
北京大学POJ
Checkout
登陆
注册
题目
6548:Checkout
题目描述
$Alice$ 是一个身怀改变世界的抱负的著名企业家,手中掌控很多著名的公司,为了更好的管理, $Alice$ 建立了一套很完善的架构体系,已知 $Alice$ 的企业的架构体系是一棵树,每个节点代表一个人。对于每个节点,它的父节点就是这个人的直接 $leader$,每个节点都有一个权值,代表这个人的爱好,每对属于同一直接 $leader$ 的节点如果有相同的爱好那么他们就会给公司产生1的和谐度,如果一个人和他/她的直接 $leader$ 的爱好相同也会给公司产生1的和谐度,但是再完美的公司都会产生离职的情况,如果一个人离职,并且这个人有直接下属,就从这个人的直接下属中选一个成为这个部门新的 $leader$,使得新的组织架构的和谐度最高,新晋的人汇报给离职的人的 $leader$(如果存在的话),同时新 $leader$ 的原来下属的直接 $leader$ 不变, $Alice$ 想知道如果某个人离职整个公司的和谐度是多少。
输入解释
第一行两个正整数 $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$
输出解释
输出一行$n$个数,第$i$个数代表如果编号为 $i$ 的人离职,公司的和谐度会是多少,以空格分隔,行末无空格。
输入样例
4 3 2 3 1 3 1 2 2 3 2 4
输出样例
1 0 1 0
来自杭电HDUOJ的附加信息
Recommend
liuyiding
该题目是Virtual Judge题目,来自
杭电HDUOJ
题目来源
2019中国大学生程序设计竞赛-女生专场(重现赛)-感谢南京晓庄学院
源链接:
HDU-6548
最后修改于
2020-10-25 23:32:13 UTC
由爬虫自动更新
共提交
0
次
通过率
--
%
时间上限
内存上限
2000/1000MS(Java/Others)
524288/524288K(Java/Others)
·
·
·
·
登陆或注册
以提交代码