407746: GYM102889 G 林克与宝箱咒语
Description
织梦岛是由 n 个地区组成的小岛,地区之间由 n - 1 条道路连接。任意两个地区都可以直接或者间接地通过道路连通,也就是说,这 n 个地区形成了一棵树。每条道路上都有一个宝箱,每个宝箱有一个种类,用 1 到 n 之间的整数来标记。
现在林克要从地区 u 出发,沿着最短的路径走到地区 v。在行走的过程中,林克可以开启他遇到的宝箱,当然也可以选择跳过遇到的宝箱。由于林克需要沿最短路径行走,当然是不能返回去开之前跳过的宝箱的。如果到达终点 v 后,林克开启的宝箱种类序列与某个古老的咒语相同,那么他将能获得一份神秘的大礼。
现在,林克还没有确定旅途的起点和终点,因此他希望你能帮他统计所有方案中有机会获得大礼的数量。具体地说,你需要统计满足下列要求的有序对 (u, v) 的数量:林克从地区 u 出发,沿最短路径走到地区 v 结束,他在路上能够合理地开启或跳过宝箱,使得开启的宝箱种类序列与古老的咒语相同。林克事先知道整个地区的地图以及每个宝箱的种类。
注意:u ≠ v 时,(u, v) 和 (v, u) 是两个不同的有序对。
Input第一行包含两个整数 n, k (1 ≤ n ≤ 105, 1 ≤ k ≤ 200)。n 表示地区的数量,k 表示古老咒语的长度。
接下来 n - 1 行,每行包含三个整数 u, v, w (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ w ≤ n)。表示地区 u 和 v 之间有一条道路,道路上的宝箱种类为 w。保证给出的 n 个地区形成了一棵树。
接下来一行包含 k 个整数 xi (1 ≤ xi ≤ n)。第 i 个整数 xi 表示古老咒语的第 i 项。
Output输出一行包含一个整数,表示答案,即问题中有序对的数量。
ExamplesInput3 1 1 2 1 1 3 1 1Output
6Input
4 2 1 2 1 1 3 2 1 4 1 1 2Output
2Input
1 1 1Output
0Note
对于第一个样例,所有的 (u, v)(u ≠ v) 均满足要求。
对于第二个样例,满足要求的有序对是 (2, 3) 和 (4, 3)。