#P5034. 果冻
果冻
题目背景
数据已经修复。
【生存世界】Steve:你们哪位 dalao 可以收留我啊 qwq……
在 Minecraft 一个很友善、和谐的服务器里面,Steve 很喜欢在里面畅游,服务器采用小镇机制,于是有很多小镇。有一个镇叫果冻镇,镇长长得很像喜欢吃果冻,他很喜欢对着镜子吃着 bling bling 的果冻。突然,他收到“捷报”,镇上不久就要造反。他吓了一跳,赶紧从床上跳了起来(qwq),吃了一口果冻(误),着手处理这件事情。
题目描述
镇上有一个镇长以及 个镇员,所有的镇员都有着他的直属上司 。每个镇镇员与镇长都有一个距离 (也就是他与镇长之间上司的人数加 )。镇长想要所有镇员都是自己的直属下司,也就是与他的距离为 。
他每分钟可以让自己的一个镇员变为自己的直属下司,在第 分钟的时候,(也就是每一分钟的意思,而 将从 开始),这个镇员变为自己的直属下司,镇长可以收获 的安全指数(其中, 为按位与运算)。然后这个镇员的下司都会跟着这个镇员一起变动(也就是这个镇员的直属下司仍然是这个镇员的,除非镇长把这个下司变为自己的直属下司)。
当所有镇员都是自己的直属下司后,镇长就可以安心吃他的果冻了。他现在想问你,应该怎样变动,才能使安全指数最大。因为镇长很想快点吃到果冻,他就把这个任务交给你了。
输入格式
第一行是两个正整数 和 (具体意义请见题目描述)。
从第二行开始,下面连续 行,每行有两个字符串(由大写字母、小写字母、下划线、数字、上引号或者逗号组成),分别表示的是这个镇员和他的直属上司。特别地,第二行是镇长,他没有直属上司,所以第二行只有一个字符串,表示镇长。数据保证第二个字符串在第一个字符串前出现过。
输出格式
一行一个整数,表示最大的安全值。
3 1
1
2 1
3 2
1
7 3
LDLD
tk_sky LDLD
Jayden_deng LDLD
only_xiaohuang tk_sky
Muddled_xiaopan tk_sky
Inkn only_xiaohuang
ipdjkl only_xiaohuang
8
提示
样例解释
第二个样例:(图片有可能会挂,请耐心等待一会哦 qwq)
由于出题人过懒,移动子节点的情况就未列举。请自行 hack 自己。(滑稽)
数据范围
记下列两种特殊情况:
- 保证字符串长度为 。
- 树退化成一条链。
对于所有的数据,保证 在int
范围内,字符串长度不超过 。 均为正整数。