#P18886. [2026多校联测]庆典
[2026多校联测]庆典
题目描述
在一片古老森林中,有一棵以 号点为根的神树,共有 个节点,由 条双向边连接。树上生活着 个部落,编号为 ,第 个部落的聚居地为节点 (多个部落可共居一处)。
现在国王希望举办 场庆典,为此需将 个部落按编号顺序划分成 个连续的非空段。每组庆典的举办地为该组所有部落聚居地的最近公共祖先(特别的,若组内只有一个部落,则举办地就是该部落的聚居地)。该组庆典的代价定义为举办地到根节点的距离(到根节点所经过的边数)。
国王当然希望各组举办庆典的代价之和最小,现在他请你求出这个最小值。
输入格式
输入第一行包含 个正整数 (,),分别表示神树的节点数,部落数量和举办庆典的次数。
输入第二行包含 个正整数,第 个数表示编号为 的部落的聚居地 ()。
接下来 行,每行两个正整数 ()表示神树上的一条无向边。
输出格式
输出一行一个非负整数,表示最小代价和。
输入输出样例
输入 #1
5 5 3
1 2 3 4 5
1 2
2 3
2 4
3 5
输出 #1
2
样例解释 #1
将部落 划分为 个非空连续段 ,代价和为 。
输入 #2
10 10 5
5 6 2 10 3 4 2 6 8 9
1 9
1 5
9 3
9 4
5 7
7 2
2 6
2 8
2 10
输出 #2
4
数据范围与约定
对于全部的数据,有
本题采用 subtask 捆绑测试,无子任务依赖。
-
子任务 1 (15分) :。
-
子任务 2 (15分) :。
-
子任务 3 (20分) :。
-
子任务 4 (10分) :。
-
子任务 5 (10分) :。
-
子任务 6 (15分) :,且树上第 条边连接了 。
-
子任务 7 (15分) :无特殊限制。