题目描述(ID:12252)
标题: 蜗牛
标签: 树结构
详情: 在一棵 N 个节点的有根树上,有一只蜗牛停在节点 P 上,其他还有 K只蜗牛停在节点 Si 上。现在这只停在 P 上的蜗牛,想要去根节点,将自己的房子停在那里。由于两只蜗牛如果同时出现在一个节点上会造成危险,所以你需要调度这些蜗牛,使得 P 到根的路径上没有别的蜗牛。可是蜗牛只能向叶子节点的方向爬,现在你希望知道所有蜗牛至少走几步(走的步数总和最小),才能使得根到 P的路径上没有别的蜗牛。
输入格式:
第一行三个数 N,P 和 K。
接下来 N 行,每行格式如下:
T A1 A2 … AT
第 i+1 行表示,第 i 个点有 T 个儿子,分别是 A1~AT。
最后一行 K 个数,表示其他 K 蜗牛的停房地点,保证 Si≠P。
输出格式:
一个数,表示其他蜗牛最少要移动多少步。
限制: 对于 40% 的数据 N≤20;
对于 100% 的数据 2≤N≤5 000,2≤P≤N,0≤K≤N-2。
样例:

输入

6 3 2
1 4
1 6
0
1 5
2 2 3
0
4 5

输出

4
登录并解答