FZU_Problem 2169 shadow

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define maxn 100001
int a[maxn],b[maxn],d[maxn],sum[maxn];
int n,m;
vector<int>v[maxn];
void bfs()
{
    queue<int>q;  //不能定义成全局变量
    for(int i=0;i<maxn;i++)
        d[i]=9999999;
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=m;i++)
    {
        q.push(b[i]);
        d[b[i]]=0;
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<v[u].size();i++)
        {
            int x=v[u][i];
            if(d[x]>d[u]+1)
            {
                d[x]=d[u]+1;
                sum[x]+=sum[u]+a[x];
                sum[u]=0;
                q.push(x);
            }
        }
    }
}

int main()
{
    int x,y,ans;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=0;i<=n;i++)
            v[i].clear();
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=m;i++)
            scanf("%d",&b[i]);
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&x,&y);
            v[x].push_back(y);
            v[y].push_back(x);
        }
        ans=0;
        bfs();
        for(int i=1;i<=n;i++)
        {
            ans+=sum[i];
        }
        printf("%d\n",ans);
    }
    return 0;
}

/*从有军队的城市BFS遍历，找到王都，沿途累加被杀掉的叛军数
用两个数组存储邻边关系
*/
#include<cstdio>
#include<cstring>
#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) //把u连在v后面
{
    L[id].val=v;  //保存v的值，且拥有唯一id 
    L[id].nxt=head[u]; //// v的next为head[u],这里head[u]表示u的头结点的id,且把它连在v的后面
    head[u]=id++;// 此时因为u的头结点已经连在v后面了,所以要更新头结点，把head[u]换成v的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;
}