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

 

题意：N<=10万个点，N-1条边使所有点连通，点编号为1~N，1号点为国王所在地，给出K个编号表示这K个点有国王的军队，给出Ai表示第i个点有Ai个叛军，国王所在地和有国王军的地方没叛军。现在国王的军队以最短路向国王所在地移动，消灭沿途所有叛军，求消灭的叛军数。

 

解：用STL的set记国王军所在地，从国王所在地开始宽搜，从当前点u扩展节点时记录扩展节点v来自哪里，from[v]=u。搜到一个国王军就把之前走的这条路上的点的叛军数加到ans里，并且对沿途的点标记geted[x]=true，一开始先标记国王所在地geted[0]=true，这样每次找到一个国王军就把国王军到geted为true的点之间的叛军数加到ans里，并且统计找到的国王军数cnt++。cnt==K时就找够全部国王军了，结束。是不是很碉，只要一次宽搜就得了耶！

1 #include
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #define MAXN 101111 9 #define RE freopen("in.txt","r",stdin); 10 11 using namespace std; 12 13 struct Edge 14 { 15 int u,v; 16 int next; 17 }; 18 Edge e[MAXN*2]; 19 int first[MAXN]; 20 int en; 21 22 void add(int u,int v) 23 { 24 e[en].u=u; 25 e[en].v=v; 26 e[en].next=first[u]; 27 first[u]=en; 28 en++; 29 } 30 31 int n,k,cnt; 32 int a[MAXN]; 33 set
             
               b; 34 bool walked[MAXN]; 35 bool geted[MAXN]; 36 queue
              
                v; 37 int from[MAXN]; 38 int farm(); 39 void init(); 40 41 int main() 42 { 43 //RE 44 while(scanf("%d%d",&n,&k)!=EOF) 45 { 46 farm(); 47 } 48 return 0; 49 } 50 51 int farm() 52 { 53 int i,j,x,y; 54 init(); 55 for(i=0; i
              
             
            
           
          
         
        
       
      

话说我交的时候突然想起set没清空，不过还是过了，难道只有一组数据…

 

 

不过耗时好像比其他方法久……好像可以手动开栈 深搜，我也不太懂怎么弄的