Accept: 373    Submit: 1462Time Limit: 1000 mSec    Memory Limit : 32768 KB

 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

 Sample Output

思路：

1、首先知道這個圖是一個無向圖，那么對應如果求出來了從u到v的最短路，那么也就等價于求出了從v到u的最短路。

那么很容易想到，對應需要求出K個軍隊到到1號節點的最短路徑都要走哪些點，其實就是要求一個單源最短路，求出從節點1到其他各個節點的最短路徑都要走哪些點。

2、那么過程維護一個數組pre【i】=x，表示以1作為源點的從1到i的最短路上，到達i之前到達的點是x。那么每一次松弛的同時，要對pre【v】進行更新。

那么我們只要一遍循環就能求出從某一個點到節點1的路徑上都經過了哪些點。

但是這里需要進行K次循環，顯然如果N比較大而且K比較大的時候會TLE.

那么我們考慮對這個圖繼續進行分析：根據題干所述，這N個點是用N-1條邊來連通的，那么顯然這個圖還是一棵樹。

那么這里同時保證，從一個點u，到點1的最短路（或者說路徑），只有一條。

那么其實在循環找前驅的過程中，如果有到達同一個點的情況（比如x,y兩個節點要到1號節點取，都共同經過了4號節點的話，那么其實在4號節點之后的路徑 ，這兩個點的路徑是重復并且相同的），那么我們過程維護一個vis【i】數組，表示之前的路徑中，是否經過了i號節點，如果已經經過了，那么肯定存在兩個節點共同經過一段重復路徑，那么之后的循環部分就可以break掉了。

3、注意處理好細節。另外，用vector存圖莫名TLE.改用鄰接表就沒問題.....

Ac代碼：

#include<stdio.h>#include<string.h>#include<vector>#include<queue>using namespace std;struct node{    int from;    int to;    int w;    int next;}e[260070];int head[160007];int cont;void add(int from,int to,int w){    e[cont].to=to;    e[cont].w=w;    e[cont].next=head[from];    head[from]=cont++;}int dis[150060];int pre[150060];int vis[150060];int a[150060];int army[150060];int n,m;void SPFA(int ss){    memset(vis,0,sizeof(vis));    memset(pre,-1,sizeof(pre));    for(int i=1;i<=n;i++)dis[i]=0x3f3f3f3f;    dis[ss]=0;    queue<int >s;    s.push(ss);    while(!s.empty())    {        int u=s.front();        //vis[u]=0;        s.pop();        for(int i=head[u];i!=-1;i=e[i].next)        {            int v=e[i].to;            if(dis[v]>dis[u]+1)            {                dis[v]=dis[u]+1;                pre[v]=u;                if(vis[v]==0)                {                    vis[v]=1;                    s.push(v);                }            }        }    }    memset(vis,0,sizeof(vis));    int output=0;    for(int i=1;i<=m;i++)    {        int now=army[i];        while(now!=-1)        {            if(vis[now]==0)            {                output+=a[now];                a[now]=0;                vis[now]=1;            }            else break;            now=pre[now];        }    }    printf("%d/n",output);}int main(){    while(~scanf("%d%d",&n,&m))    {        int cont=0;        memset(head,-1,sizeof(head));        for(int i=1;i<=n;i++)        {            scanf("%d",&a[i]);        }        for(int i=1;i<=m;i++)        {            scanf("%d",&army[i]);        }        for(int i=0;i<n-1;i++)        {            int x,y;            scanf("%d%d",&x,&y);            add(x,y,1);            add(y,x,1);        }        SPFA(1);    }}