Problem Description
YL是shadow国的国王,shadow国有N个城市。为了节省开支,shadow国只有N-1条道路,这N-1条道路使得N个城市连通。某一年,shadow国发生了叛乱,叛军占领了多个城市,王都岌岌可危。王都为编号为1的城市，除了王都外有K个城市有YL的军队。现在这K支军队要向王都进军，并且消灭沿途经过的城市中的叛军。现给出N个城市的道路情况以及城市的叛军数量，问总共需要消灭多少叛军？
Input
第一行输入两个整数N，K，接下来输入N(1<=N<=100000)个整数Ai(0<=Ai<=10000)，表示第i个城市的叛军数量。接下来输入K个大于等于1且小于等于N的整数，表示有军队的城市的编号。数据保证王都以及有军队的城市没有叛军。接下来输入N-1行，每行两个整数u、v，表示连接u和v的一条道路。每支军队只能沿着道路走，并且是其所在城市与王都之间的最短路线走。
Output
输出一行一个整数表示消灭的叛军数量。
Sample Input
4 2
0 3 0 0
3 4
1 2
2 3
2 4
Sample Output
3
代码：
/**
* 从有军队的城市BFS遍历，找到王都，沿途累加被杀掉的叛军数
* 用两个数组存储邻边关系
*/
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
#define N 100005
struct list{
int val;
int nxt;
}L[N * 2]; //储存相邻边的关系
struct point{
int val;
int k_num;//杀死敌军数
}p, q;
int enemy[N];//叛军
int army[N]; //国军
int vis[N]; //标记是否被访问
int head[N];
int n, k, id;
void add(int u, int v)
{
L[id].val = v;
L[id].nxt = head[u];
head[u] = id++;
}
int bfs(int x)
{
int ret = 0;
queue<point> s;
p.val = x;
p.k_num = enemy[x];
s.push(p);
vis[x] = 1;
while (!s.empty())
{
p = s.front();
s.pop();
if (1 == p.val)
ret = p.k_num;
for (int i = head[p.val]; i != 0; i = L[i].nxt)
{
int v = L[i].val;
if (0 == vis[v])
{
vis[v] = 1;
q.val = v;
q.k_num = p.k_num + enemy[v];
s.push(q);
}
}
}
return ret;
}
int main()
{
while (scanf("%d%d", &n, &k) != EOF)
{
for (int i = 1; i <= n; i++)
scanf("%d", &enemy[i]);
for (int i = 1; i <= k; i++)
scanf("%d", &army[i]);
memset(vis, 0, sizeof(vis));
memset(head, 0, sizeof(head));
int ans = 0;
id = 1;
for (int i = 1; i <= n - 1; i++)
{
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
add(v, u);
}
for (int i = 1; i <= k; i++){
if (0 == vis[army[i]])
ans += bfs(army[i]);
}
printf("%d\n", ans);
}
return 0;
}