学步园

树形DP

题意： 在一棵树上的某个节点有一本书，在这本书附近的距离d范围内的节点会出现鬼怪，现在给出部分鬼怪的位置，问书的位置有几种可能。节点数10W。

解法：简单分析知，若一个节点和鬼怪的最远距离大于d，那么书就不可能在这里。设dp[u][0],dp[u][1]分别为以u为根的子树中鬼怪距离根节点的最远距离和次远距离，这个在第一遍dfs就可以全部求出。然后第二遍dfs将父节点的最远距离传入子节点，就可以知道子节点距离鬼怪的最远距离，统计一下就可以了。

类似的题也做过几道，可是比赛的时候到最后20分钟才有大概的思路，也没想敲了。不管是手速还是思维都弱啊。

邻接表开小导致WA了两发，ORZ。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define clr(a,b) memset(a,b,sizeof(a))
typedef long long lld;
const int INF = ~0u>>1;

int dp[101000][2];
int pre[101000][2];
int n,m,d;
struct Edge {
    int v, next;
}g[201000];
int head[101000], tot;
int cnt;

void add_edge(int u, int v) {
    g[tot].v = v;
    g[tot].next = head[u];
    head[u] = tot ++;
}

void dfs(int u, int fa) {
    for(int p=head[u]; ~p; p=g[p].next) {
        if(g[p].v == fa) continue;
        int v = g[p].v;
        dfs(v,u);
        if(dp[v][0]+1 > dp[u][1]) {
            dp[u][1] = dp[v][0] + 1;
            pre[u][1] = v;
            if(dp[u][1] > dp[u][0]) {
                swap(dp[u][1],dp[u][0]);
                swap(pre[u][1],pre[u][0]);
            }
        }
    }
}

void dfs2(int u, int fa, int dis) {
    if(dis > d) return ;
    if(dp[u][0] <= d) cnt ++;
    int d1 = max(dis, dp[u][0]) + 1;
    int d2 = max(dis, dp[u][1]) + 1;
    for(int p=head[u]; ~p; p=g[p].next) {
        if(g[p].v == fa) continue;
        int v = g[p].v;
        if(pre[u][0] == v) dfs2(v,u,d2);
        else dfs2(v,u,d1);
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &d);
    int x;
    REP(i,1,n+1) dp[i][0] = dp[i][1] = -10000000;
    clr(head, -1);
    REP(i,1,m+1) scanf("%d", &x), dp[x][0] = 0;

    int a,b;
    REP(i,1,n) {
        scanf("%d%d", &a, &b);
        add_edge(a,b);
        add_edge(b,a);
    }
    dfs(1,-1);
    dfs2(1,-1,-10000000);
    printf("%d\n", cnt);
    return 0;
}