#P10406. 「SMOI-R1」Company

「SMOI-R1」Company

题目背景

LAR 被老板炒了,下面都是他的梦。

题目描述

城市中有 nn 所公司,第 ii 所公司有 mim_i 个人。

一所公司可以用一棵根为 11树来表示,最初时节点 11 是老板,每个节点的子节点都是他的下属,每个节点的父节点都是他的上司。第 ii 棵树的大小为 mim_i,节点从 11mim_i 编号。

公司很多,政府管理起来非常麻烦,所以政府想让 LAR 把这些公司合并起来。两所公司要合并起来,需要一所公司的一名最初没有下属的人(员工或老板)成为另一所公司现在的老板的上司。当两个公司合并完,两所公司就是一所公司了。

只有互为上司和下属的两个人才认识。

myz 是第 11 棵树的节点 xx,ljs 是第 22 棵树的节点 yy。因为 myz 和 ljs 性格十分不相符(他们不认识),所以 LAR 想让他们的关系越远越好

互相认识的人距离为 11两人的关系定义为两人的人际关系网上的最短距离(可以简单认为是最终形成的树中两点的最短距离)。例如,11 认识 2222 认识 33,那么 1133 的关系就是 22

输入格式

第一行有一个整数 nn,代表公司数量。

第二行到第 n+1n+1 行中,第 i+1i + 1 行第一个整数是 mim_i,代表第 ii 所公司的人的数量。接下来有 mi1m_i - 1 个整数,第 jj 个数代表这棵树中节点 j+1j+1 的上司。

n+2n+2 行有两个整数 xxyy,代表 myz 是第 11 棵树的节点 xx,ljs 是第 22 棵树的节点 yy

输出格式

输出一个整数,代表 myz 和 ljs 关系的最大值。

3
3 1 1
3 1 2
4 1 2 1
2 3
8

提示

样例解释

在还没有进行合并操作时,城市中公司如下(括号中的数是节点初始时所在的公司):

想要让关系值最大,可以让最终的公司形成下图的样子:

答案为 88

数据范围

本题采用捆绑测试

subtask编号 nn\leq m\sum m \leq 特殊情况 分值
11 22 10310^3 2020
22 10510^5 10610^6 x=1x = 1y=1y=1
33 所有树都是随机树
44 4040

随机树产生规则:对于节点 ii2im2 \le i \le m)的上司从 11i1i - 1等概率产生。

对于 100%100\% 的数据,2n1052\leq n\leq 10^51mi1 \le m_im106\sum m \leq 10^61xm11\leq x\leq m_11ym21\leq y\leq m_2