CodeForces #196(Div. 2) 337D Book of Evil （樹形dp）

題目： 點擊打開鏈接

題意
給一棵n個結點的樹，任意兩個節點的距離是指連接兩點的最短的邊數
在樹上的某個結點有一個“惡魔之書”，這本書會讓距離它d以內的節點都受到影響
已知有m個節點收到了影響，問最多有幾個結點可能放著“惡魔之書”？

思路
要判斷某個點是不是放著書，就要判斷這個點的周圍d距離以內是否包含所有受影響的m節點
而如果某個節點距離最遠的那個受影響節點的距離是L,如果L <= d，那麼說明所有受影響的m節點都在d以內，就可判斷這個點可能放著書

那麼，我們只要能夠求出每個節點距離最遠的影響節點是多少，就可以O(n)的時間求出答案了。

所以可以用樹形dp求解：

f(u, 0): 表示u為頂點的子樹中，距u最遠的“受影響節點”的距離
f(u, 1): 表示整個樹刪去u為頂點的子樹,但是依舊保留u點為頂點，這個樹中距離u最遠的“受影響節點”的距離

所有的f(u, 0)可以一次dfs搞定, O(n)
f(u, 1)可以由頂節點一直推下去

f(v, 1) = max{f[brother1][0], f[brother2][0]..., f[brother3][0], f[father][1] | brother是v的兄弟節點，fa是v的父節點} + 1

這一步可以再一次dfs解決，同樣是O(n)

代碼

**========================================== *
   This is a solution for ACM/ICPC problem * *  
 @source：CodeForces 337D Book of Evil *  
 @type: 樹形dp *  

 @author: shuangde *   
@blog: blog.csdn.net/shuangde800 *  
 @email: [email protected] *===========================================*
/#include <iostream>#include 
<cstdio>#include
 <algorithm>#include 
<vector>#include
 <queue>#include 
<cmath>#include 
<cstring>#define MP make_pairusing namespace std;
typedef long long int64;t
ypedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const double PI  = acos(-1.0);const int MAXN = 1e5+10;
namespace Adj{    int head[MAXN], size;   
 struct Node{        int v, next;  
   }E[MAXN*2+100];  
  void initAdj() {        size = 0;         
memset(head, -1, sizeof(head));
    }    void addEdge(int u, int v) {        E[size].v = v;  
      E[size].next = head[u];     
   head[u] = size++;  
  }}using namespace Adj;int n, m, d;int f[MAXN][2];
bool vis[MAXN], p[MAXN];int ans;void dfs(int u) {    vis[u] = true;  
  int& ans = f[u][0] = (p[u] ? 0 : -1);  
  for (int e = head[u]; e != -1; 
e = E[e].next) {        int v = E[e].v;  
      if (vis[v]) continue;     
   dfs(v);   
     if (f[v][0] != -1)          
   ans = max(ans, f[v][0] + 1);   
 }}// 維護m1,m2保存第一大，第二大inline void update(int w, int v, 
PII& m1, PII& m2) {    if (w >= m1.first) {     
   m2 = m1; m1.first = w; m1.second = v;    
} else if (w >= m2.first) {        m2.first = w; 
m2.second = v;    }}void dp(int u) {    vis[u] = true;   
 PII m1 = MP(-1, 0), m2=MP(-1, 0);    
int tmp = max(f[u][0], f[u][1]);  
  if (tmp != -1 && tmp <= d) {        ++ans;    
 }    update(f[u][1], u, m1, m2);   
 for (int e = head[u]; e != -1; e = E[e].next) {        int v = E[e].v;     
   if (vis[v]) continue;    
     if (f[v][0] != -1) {            update(f[v][0]+1, v, m1, m2);  
      }    }    for (int e = head[u]; e != -1; e = E[e].next) {   
     int v = E[e].v;  
      if (vis[v]) continue;       
  f[v][1] = -1;     
   if (v!=m1.second && m1.first!=-1) {        
    f[v][1] = max(f[v][1], m1.first+1);    
    } else if (m2.first != -1) {            f[v][1] = max(f[v][1], m2.first+1);  
      }        dp(v); 
   }}int main(){    while (~scanf("%d%d%d"
, &n, &m, &d)) {        initAdj();    

    memset(p, 0, sizeof(p));       
 for (int i = 0; i < m; ++i) {            int x;   
         scanf("%d", &x);        
    p[x] = true;   
     }         for (int i = 0; i < n - 1; ++i) {            int u, v;     
       scanf("%d%d", &u, &v);        
    addEdge(u, v);       
     addEdge(v, u);   
     }        memset(vis, 0, sizeof(vis));     
   dfs(1);     
   f[1][1] = p[1]?0:-1;   
     ans = 0;   
     memset(vis, 0, sizeof(vis));   
     dp(1);        
printf("%d\n", ans);  
  }    return 0;}