FZU 2169 shadow (用了一次鄰接表存邊，樹形DP)

Accept: 28 Submit: 97
Time 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的一條道路。每支軍隊只能沿著道路走，並且是其所在城市與王都之間的最短路線走。<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KCjxoMj48aW1nIHNyYz0="https://www.aspphp.online/bianchen/UploadFiles_4619/201701/2017012114355696.gif" alt="\"> Output

輸出一行一個整數表示消滅的叛軍數量。

Sample Input

Sample Output

#include
#include
typedef struct nnn
{
    int id;
    struct nnn *next;
}*NODE,node;
NODE edg[200005];
int dp[200005],flog[200005],value[200005],vist[200005];
void dfs(int p)
{
    NODE NEXT,q;
    dp[p]=value[p]; vist[p]=1;
    for(NEXT=edg[p]->next; NEXT!=NULL; )
    {
        int son=NEXT->id;
        if(vist[son]){
          NEXT=NEXT->next;  continue;
        }
        dfs(son);
        if(flog[son])
        {
            flog[p]=1; dp[p]+=dp[son];
        }
        q=NEXT;
        NEXT=NEXT->next;
    }
}
int main()
{
    int n,k,a,b,i;
    NODE p;
    while(scanf("%d%d",&n,&k)>0)
    {
        for(i=0;i<=n;i++)
        {
            flog[i]=0; vist[i]=0;
            edg[i]=(NODE)malloc(sizeof(node));
            edg[i]->next=NULL;
        }
        for(i=1; i<=n; i++)
            scanf("%d",&value[i]);
        for(i=1; i<=k; i++)
        {
            scanf("%d",&a);
            flog[a]=1;
        }
        for(i=1; iid=b; p->next=edg[a]->next;
            edg[a]->next=p;
             p=(NODE)malloc(sizeof(node));
            p->id=a; p->next=edg[b]->next;
            edg[b]->next=p;
        }
        dfs(1);
        printf("%d\n",dp[1]);
    }
}