{"trustable":true,"sections":[{"title":"题目描述","value":{"format":"MD","content":"**题目译自 [JOISC 2020](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/index.html) Day4 T1「[首都](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/day4/capital_city.pdf) / [Capital City](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/day4/capital_city-en.pdf)」**\r\n\r\n在 JOI 的国度有 $N$ 个小镇,从 $1$ 到 $N$ 编号,并由 $N-1$ 条双向道路连接。第 $i$ 条道路连接了 $A_i$ 和 $B_i$ 这两个编号的小镇。\r\n\r\n这个国家的国王现将整个国家分为 $K$ 个城市,从 $1$ 到 $K$ 编号,每个城市都有附属的小镇,其中编号为 $j$ 的小镇属于编号为 $C_j$ 的城市。每个城市至少有一个附属小镇。\r\n\r\n国王还要选定一个首都。首都的条件是该城市的任意小镇都只能通过属于该城市的小镇到达。\r\n\r\n但是现在可能不存在这样的选址,所以国王还需要将一些城市进行合并。对于合并城市 $x$ 和 $y$ ,指的是将所有属于 $y$ 的小镇划归给 $x$ 城。\r\n\r\n你需要求出最少的合并次数。"}},{"title":"输入格式","value":{"format":"MD","content":"输入第一行两个整数 $N,K$,为小镇和城市的数量。\r\n\r\n接下来的 $N-1$ 行,每行两个整数 $A_i,B_i$,描述了 $N-1$ 条道路。\r\n\r\n再接下来的 $N$ 行,每行一个整数 $C_j$,表示编号为 $j$ 的小镇属于编号为 $C_j$ 的城市。"}},{"title":"输出格式","value":{"format":"MD","content":"输出一行一个整数为最少的合并次数。"}},{"title":"样例 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e6 3\n2 1\n3 5\n6 2\n3 4\n2 3\n1\n3\n1\n2\n3\n2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n你可以对城市 $1$ 和 $3$ 进行合并,然后选定 $1$ 为首都,因为最初任何城市都无法作为首都。总花费为 $1$ 。\n\n这个样例满足子任务 $1,2,4$。"}},{"title":"样例 2","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e8 4\n4 1\n1 3\n3 6\n6 7\n7 2\n2 5\n5 8\n2\n4\n3\n1\n1\n2\n3\n4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n这个样例满足子任务 $1,2,3,4$。"}},{"title":"样例 3","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e12 4\n7 9\n1 3\n4 6\n2 4\n10 12\n1 2\n2 10\n11 1\n2 8\n5 3\n6 7\n3\n1\n1\n2\n4\n3\n3\n2\n2\n3\n4\n4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n这个样例满足子任务 $1,2,4$。"}},{"title":"数据范围与提示","value":{"format":"MD","content":"对于 $100\\%$ 的数据,$1\\leq N\\leq 2\\times 10^5$,保证:\r\n\r\n- $1\\leq K\\leq N$;\r\n\r\n- $1\\leq A_i,B_i\\leq N(1\\leq i\\leq N-1)$;\r\n\r\n- 从任何一个小镇出发都能到达其他任何小镇;\r\n\r\n- $1\\leq C_j\\leq K(1\\leq j\\leq N)$;\r\n\r\n- 对于每一个 $k(1\\leq k\\leq K)$,存在一个 $j(1\\leq j\\leq N)$,使得 $C_j\u003dk$。\r\n\r\n详细子任务及附加限制如下表所示:\r\n\r\n| 子任务编号 | 附加限制 | 分值 |\r\n| :--------: | :--------------------: | :--: |\r\n| $1$ | $N\\leq 20$ | $1$ |\r\n| $2$ | $N\\leq 2000$ | $10$ |\r\n| $3$ | 每个小镇最多可通过公路与两个小镇直接相连 | $30$ |\r\n| $4$ | 无附加限制 | $59$ | "}}]}