#P10406. 「SMOI-R1」Company
「SMOI-R1」Company
题目背景
LAR 被老板炒了,下面都是他的梦。
题目描述
城市中有 所公司,第 所公司有 个人。
一所公司可以用一棵根为 的树来表示,最初时节点 是老板,每个节点的子节点都是他的下属,每个节点的父节点都是他的上司。第 棵树的大小为 ,节点从 到 编号。
公司很多,政府管理起来非常麻烦,所以政府想让 LAR 把这些公司合并起来。两所公司要合并起来,需要一所公司的一名最初没有下属的人(员工或老板)成为另一所公司现在的老板的上司。当两个公司合并完,两所公司就是一所公司了。
只有互为上司和下属的两个人才认识。
myz 是第 棵树的节点 ,ljs 是第 棵树的节点 。因为 myz 和 ljs 性格十分不相符(他们不认识),所以 LAR 想让他们的关系越远越好。
互相认识的人距离为 ,两人的关系定义为两人的人际关系网上的最短距离(可以简单认为是最终形成的树中两点的最短距离)。例如, 认识 , 认识 ,那么 和 的关系就是 。
输入格式
第一行有一个整数 ,代表公司数量。
第二行到第 行中,第 行第一个整数是 ,代表第 所公司的人的数量。接下来有 个整数,第 个数代表这棵树中节点 的上司。
第 行有两个整数 和 ,代表 myz 是第 棵树的节点 ,ljs 是第 棵树的节点 。
输出格式
输出一个整数,代表 myz 和 ljs 关系的最大值。
3
3 1 1
3 1 2
4 1 2 1
2 3
8
提示
样例解释
在还没有进行合并操作时,城市中公司如下(括号中的数是节点初始时所在的公司):
想要让关系值最大,可以让最终的公司形成下图的样子:
答案为 。
数据范围
本题采用捆绑测试。
subtask编号 | 特殊情况 | 分值 | ||
---|---|---|---|---|
无 | ||||
, | ||||
所有树都是随机树 | ||||
无 |
随机树产生规则:对于节点 ()的上司从 到 中等概率产生。
对于 的数据,,,,,。