Codeforces 377D Book of Evil

题意：给你一棵树，有些节点有恶魔，恶魔有统一的影响范围，问你被所有恶魔都影响到的点有多少个。

解题思路：树形dp，难点就在于如何在从上往下的过程中消除掉从下往上的影响，我的方法就是记录一个 secdp值，来维护那个最小的距离。

解题代码：

  1 // File Name: 337d.cpp
  2 // Author: darkdream
  3 // Created Time: 2015年03月13日 星期五 20时18分05秒
  4 
  5 #include<vector>
  6 #include<list>
  7 #include<map>
  8 #include<set>
  9 #include<deque>
 10 #include<stack>
 11 #include<bitset>
 12 #include<algorithm>
 13 #include<functional>
 14 #include<numeric>
 15 #include<utility>
 16 #include<sstream>
 17 #include<iostream>
 18 #include<iomanip>
 19 #include<cstdio>
 20 #include<cmath>
 21 #include<cstdlib>
 22 #include<cstring>
 23 #include<ctime>
 24 #define LL long long
 25 #define maxn 100010
 26 using namespace std;
 27 int n , m, d; 
 28 vector<int> mp[maxn];
 29 int color[maxn];
 30 int dis[maxn];
 31 int dp[maxn];
 32 int secdis[maxn];
 33 int sum[maxn];
 34 void dfs(int k , int la)
 35 {
 36     if(color[k] == 1 )
 37     {
 38        dp[k] = 1; 
 39     }
 40     dis[k] = d; 
 41     secdis[k] = d; 
 42     for(int i= 0;i < mp[k].size();i ++)
 43     {
 44        if(mp[k][i] == la)
 45            continue;
 46        dfs(mp[k][i],k);
 47        if(dis[mp[k][i]] >= 1  && dp[mp[k][i]] != 0) 
 48        {
 49            dp[k] += dp[mp[k][i]];
 50            if(dis[mp[k][i]] - 1 <= dis[k])
 51            {
 52               secdis[k] = dis[k];
 53               dis[k] = dis[mp[k][i]] - 1; 
 54            }
 55        }
 56     }
 57     sum[k] += dp[k];
 58 }
 59 void dfs1(int k,int la,int ladis,int laval)
 60 {
 61     //printf("%d %d %d %d
",k,la,ladis,laval);
 62     if(ladis < 0 || laval == 0)
 63     {
 64         laval = 0 ; 
 65         ladis = d ; 
 66     }else{
 67        sum[k] += laval;
 68     }
 69     for(int i = 0;i < mp[k].size();i ++)
 70     {
 71         int tt = laval;
 72         int ttd = ladis;
 73         if(mp[k][i] == la)
 74             continue;
 75         //printf("***
");
 76         if(dis[mp[k][i]] == dis[k]+1)
 77         {
 78             ttd = min(ladis,secdis[k]);
 79         }else{
 80             ttd = min(ladis,dis[k]);
 81         }
 82         if(dis[mp[k][i]] != 0)
 83           tt += dp[k] - dp[mp[k][i]];
 84         else 
 85           tt += dp[k];
 86         dfs1(mp[k][i],k,ttd-1,tt);
 87     }
 88 }
 89 int main(){
 90     scanf("%d %d %d",&n,&m,&d);
 91     int tmp = 0 ; 
 92     for(int i = 1;i <= m;i ++)
 93     {
 94        scanf("%d",&tmp);
 95        color[tmp] = 1;
 96     }
 97     int ta, tb;
 98     for(int i = 1;i < n;i ++)
 99     {
100         scanf("%d %d",&ta,&tb);
101         mp[ta].push_back(tb);
102         mp[tb].push_back(ta);
103     }
104     dfs(1,0);
105     dfs1(1,0,0,0);
106     int ans = 0 ; 
107     for(int i = 1;i <= n;i ++)
108         if(sum[i] == m)
109             ans ++;
110     printf("%d
",ans);
111 return 0;
112 }

View Code

没有梦想，何谈远方