#P18886. [2026多校联测]庆典

[2026多校联测]庆典

题目描述

在一片古老森林中,有一棵以 11 号点为根的神树,共有 nn 个节点,由 n−1n-1 条双向边连接。树上生活着 mm 个部落,编号为 1∼m1∼m ,第 ii 个部落的聚居地为节点 aia_i​(多个部落可共居一处)。

现在国王希望举办 kk 场庆典,为此需将 mm 个部落按编号顺序划分成 kk 个连续的非空段。每组庆典的举办地为该组所有部落聚居地的最近公共祖先(特别的,若组内只有一个部落,则举办地就是该部落的聚居地)。该组庆典的代价定义为举办地到根节点的距离(到根节点所经过的边数)。

国王当然希望各组举办庆典的代价之和最小,现在他请你求出这个最小值。

输入格式

输入第一行包含 33 个正整数 n,m,kn,m,k (3≤k≤m≤1063\leq k\leq m\leq 10^6,3≤n≤1063\leq n\leq 10^6),分别表示神树的节点数,部落数量和举办庆典的次数。

输入第二行包含 mm 个正整数,第 ii 个数表示编号为 ii 的部落的聚居地 aia_i (1≤ai≤n1\leq a_i\leq n)。

接下来 n−1n-1 行,每行两个正整数 x,yx,y(1≤x,y≤n1\leq x,y\leq n)表示神树上的一条无向边。

输出格式

输出一行一个非负整数,表示最小代价和。

输入输出样例

输入 #1

5 5 3
1 2 3 4 5
1 2
2 3
2 4
3 5

输出 #1

2

样例解释 #1

将部落 [1,2,3,4,5][1,2,3,4,5] 划分为 33 个非空连续段 [1][2,3][4,5][1][2,3][4,5],代价和为 0+1+1=20+1+1=2。

输入 #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

数据范围与约定

对于全部的数据,有 3≤k≤m≤106,3≤n≤1063\leq k\leq m\leq 10^6,3\leq n\leq10^6

本题采用 subtask 捆绑测试,无子任务依赖。

  • 子任务 1 (15分) :n,m≤100n,m\leq 100。

  • 子任务 2 (15分) :n,m≤1000n,m\leq 1000。

  • 子任务 3 (20分) :n,m≤5×104n,m\leq 5\times 10^4。

  • 子任务 4 (10分) :n,m≤2×105n,m\leq 2\times 10^5。

  • 子任务 5 (10分) :n,m≤105,k≤5n,m\leq 10^5,k\leq 5。

  • 子任务 6 (15分) :n≤105n\leq 10^5,且树上第 ii 条边连接了 i,i+1i,i+1。

  • 子任务 7 (15分) :无特殊限制。