← 返回题目列表

Codeforces · 348/E

E. 朝圣者

中文机器翻译题面 查看原题

很久以前,有一个叫做杜德兰的土地。杜德兰 (Dudeland) 由 n 个城镇组成,有 n - 1 条双向道路相连。城镇的索引从 1 到 n,如果沿着该国的道路行驶,可以从任何其他城市到达任何城市。杜德兰有 m 座修道院,分布在 m 个不同的城镇。每个修道院里都住着一位朝圣者。

年初,每位朝圣者都会写下距离自己居住的寺院最远的寺院。如果有多个最远的寺院,他会全部列出。在大勒博斯基日,每个朝圣者从他的报纸上随机选择一个城镇,然后开始步行前往该城镇。

沃尔特讨厌朝圣者,并希望阻止他们完成旅程,让尽可能多的人不高兴。他计划摧毁一座没有修道院的城镇。如果朝圣者从他所居住的修道院无法访问列表中的所有修道院,他会感到不高兴。

你需要找到沃尔特能让朝圣者不高兴的最大数量。还要找出他可以让最大数量的朝圣者不高兴的方法的数量:他可以摧毁的可能城镇的数量。

输入

第一行包含两个整数 n (3 ≤ n ≤ 105) 和 m (2 ≤ m < n)。下一行包含 m 个不同的整数,表示包含修道院的城镇的索引。

接下来的 n - 1 行分别包含三个整数 ai、bi、ci,表示城镇 ai 和 bi 之间有一条长度为 ci 的边(1 ≤ ai,bi ≤ n,1 ≤ ci ≤ 1000,ai ≠ bi)。

输出

输出两个整数:Walter最多可以让多少个朝圣者不高兴,以及他可以让他的计划实现的方式数量。

示例

输入 #1

8 5
7 2 5 4 8
1 2 1
2 3 2
1 4 1
4 5 2
1 6 1
6 7 8
6 8 10

输出 #1

5 1