做题感悟：开始做时用的 Dijkstra 记录每个节点的父亲节点然后从有军队的城市向1城市出发，因为互相连通，所以每个城市的根节点都为 1 ，但是只用Dijkstra 就足以超时
。
解题思路：其实不需要用Dijkstra 因为如果把 1 节点看作根节点，那么，每个节点（根节点父亲为自己）必定只有一个父亲节点，只需要从根节点BFS一次就找到每个节点的父亲节点，而且必定最短路（只有n-1条道路，而且互相连通，说明此图为一棵树），然后从有军队的节点出发一直到根节点，如果军队一（节点）找到的父亲是之前某个军队找过的节点，那么就不需要继续找了（因为接下来的走的路一样）。
代码：
#include<stdio.h>
#include<iostream>
#include<map>
#include<stack>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std ;
#define lld __int64
#define pret(a,b) memset(a,b,sizeof(a))
const double PI = 3.1415926 ;
const double esp = 1e-7 ;
const int INF = 999999999 ;
const int MX = 200005 ;
int n,k,top ;
bool vis[MX] ;
int f[MX],num[MX],g[MX] ;
struct Vext
{
int head ;
}V[MX] ;
struct Edge
{
int v,next ;
}E[MX] ;
void bfs(int x) // 寻找所有城市的父亲
{
memset(vis,false,sizeof(vis)) ;
queue<int>q ;
vis[x]=true ;
q.push(x) ;
while(!q.empty())
{
x=q.front() ;
q.pop() ;
for(int i=V[x].head ;i!=-1 ;i=E[i].next)
{
int u=E[i].v ;
if(vis[u]) continue ;
f[u]=x ;
vis[u]=true ;
q.push(u) ;
}
}
}
void add_edge(int u,int v)
{
E[top].v=v ;
E[top].next=V[u].head ;
V[u].head=top++ ;
}
void init()
{
top=0 ;
pret(V,-1) ;
for(int i=0 ;i<=n ;i++)
f[i]=i ;
}
int main()
{
int u,v ;
while(~scanf("%d%d",&n,&k))
{
init() ;
for(int i=1 ;i<=n ;i++)
scanf("%d",&num[i]) ;
for(int i=0 ;i<k ;i++)
scanf("%d",&g[i]) ;
for(int i=0 ;i<n-1 ;i++)
{
scanf("%d%d",&u,&v) ;
add_edge(u,v) ;
add_edge(v,u) ;
}
bfs(1) ; // 找父亲
memset(vis,false,sizeof(vis)) ;
int sum=0 ;
for(int i=0 ;i<k ;i++) // 回溯到根节点
{
u=g[i] ;
if(vis[u]) continue ;
vis[u]=true ;
while(1)
{
v=f[u] ;
if(vis[v]||v==1) break ;
vis[v]=true ;
sum+=num[v] ;
u=v ;
}
}
printf("%d\n",sum) ;
}
return 0 ;
}