天天看点

FZU2168 防守阵地 I

FZU2168 防守阵地 I

yl是shadow国的国王,shadow国有n个城市。为了节省开支,shadow国只有n-1条道路,这n-1条道路使得n个城市连通。某一年,shadow国发生了叛乱,叛军占领了多个城市,王都岌岌可危。王都为编号为1的城市,除了王都外有k个城市有yl的军队。现在这k支军队要向王都进军,并且消灭沿途经过的城市中的叛军。现给出n个城市的道路情况以及城市的叛军数量,问总共需要消灭多少叛军?

FZU2168 防守阵地 I

第一行输入两个整数n,k,接下来输入n(1<=n<=100000)个整数ai(0<=ai<=10000),表示第i个城市的叛军数量。接下来输入k个大于等于1且小于等于n的整数,表示有军队的城市的编号。数据保证王都以及有军队的城市没有叛军。接下来输入n-1行,每行两个整数u、v,表示连接u和v的一条道路。每支军队只能沿着道路走,并且是其所在城市与王都之间的最短路线走。

FZU2168 防守阵地 I

输出一行一个整数表示消灭的叛军数量。

FZU2168 防守阵地 I

4 2

0 3 0 0 

3 4

1 2

2 3

2 4

FZU2168 防守阵地 I

3

dp