UOJ Logo Universal Online Judge

UOJ

#11. 【UTR #1】ydc的大树

统计

ydc有一棵$n$个结点的黑白相间的大树,从$1$到$n$编号。

这棵黑白树中有$m$个黑点,其它都是白点。

对于一个黑点我们定义他的好朋友为离他最远的黑点。如果有多个黑点离它最远那么都是它的好朋友。两点间的距离定义为两点之间的最短路的长度。

现在你要摧毁一个白点。

摧毁后有一些黑点会不高兴。一个黑点不高兴当且仅当他不能到达任何一个在摧毁那个白点前的好朋友。

请你最大化不高兴的黑点数。

输入格式

第一行包含两个正整数$n,m$ $(2\le m < n)$,分别表示树的结点数,以及黑点数。

接下来$1$行,有$m$个互不相同的正整数,表示每个黑结点的编号。

接下来$n-1$行,每行三个正整数$u,v,l$,表示结点 $u,v$ 之间有一条无向边长度为 $l$。

输出格式

共一行,两个数,分别表示:最多能让多少个黑点不高兴,以及有多少种方式达到这种效果。(即统计有多少个白点摧毁后能使黑点不高兴的个数最大化)

样例一

input

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

output

5 1

样例二

input

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

output

0 2

样例三

见样例数据下载。

限制与规定

测试点编号 $n$的规模 备注
1$n \le 10^2$
2
3$n \le 10^3$
4
5
6$n \le 10^5$保证是一条链
7$n \le 10^5$$2 \le m \le 10$
8$n \le 10^5$
9
10

保证对于每条边,边权满足 $1 \le l \le 1000$。

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载