樹形dp-CF-337D. Book of Evil

題目鏈接：

http://codeforces.com/problemset/problem/337/D

題目大意：

給一棵樹，m個點，一個距離d，求有多少個點A,使得A到所有的m個點距離都不超過d.

解題思路：

樹形dp.

有兩種方法可以解：

1、類似于樹的直徑的求法，先以任意一點作為樹根，找到距離該點最遠的m中的A點（A點一定是m個點中距離相距最遠的兩點的一個端點），然后以A點作為樹根，依次計算各點到A點的最短距離d1[]，并找到距離最遠的m中的點B點,然后以B點為樹根，依次找到各點到B點的距離d2[]. ?最后再掃一遍，找到d1和d2都不超過d的點。這種方法求比較簡單。

2、先以m中任意一點為樹根，在子樹中，求出每個節點到達m中的點的最大距離max1,達到max1的直接兒子pre,次大距離。然后再從該根出發，遞歸維護一個值從父親過來并且不是通過該節點的最大距離。每次求兒子時判斷下，是不是等于該節點的pre,如果是的話，從次大中找。

樹很靈活，遞歸很強大。多做些樹上的題。

代碼：

?

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
#define Maxn 110000
//
struct Node
{int max1,max2,pre; //只用保存在子樹中，該點到給定點的最大距離、次大距離以及最大距離的直接兒子編號//向下推進的時候，維護一個從父親到達該點的最大值
}node[Maxn];struct Edge
{int v;struct Edge *next;
}*head[Maxn<<1],edge[Maxn<<1]; //無向邊
bool pm[Maxn];
int n,m,d,ans,cnt;void add(int a,int b)
{++cnt;edge[cnt].v=b;edge[cnt].next=head[a],head[a]=&edge[cnt];
}
void dfs1(int pre,int cur)
{if(pm[cur]) //如果是給定的點 距離為0，否則置為無窮大node[cur].max1=node[cur].max2=0;elsenode[cur].max1=node[cur].max2=-INF;struct Edge * p=head[cur];while(p){if(p->v!=pre){dfs1(cur,p->v);//先求出兒子if(node[p->v].max1+1>=node[cur].max1) //用兒子來更新最大值{node[cur].max2=node[cur].max1;//更新次大值node[cur].max1=node[p->v].max1+1;node[cur].pre=p->v;}else{  //更新次大值if(node[p->v].max1+1>node[cur].max2)node[cur].max2=node[p->v].max1+1;}}p=p->next;}
}
void dfs2(int pre,int cur,int pa) //往下遞歸的時候，順便判斷，決定出來
{if(max(node[cur].max1,pa)<=d) //從父親和孩子的最大距離不超過d的話，肯定是可以的ans++;struct Edge * p=head[cur];while(p){if(p->v!=pre){if(p->v==node[cur].pre) //如果最大值是從該兒子更新過來的，從次大值中選dfs2(cur,p->v,max(node[cur].max2,pa)+1);elsedfs2(cur,p->v,max(node[cur].max1,pa)+1);}p=p->next;}
}int main()
{int a,b,aa;while(~scanf("%d%d%d",&n,&m,&d)){memset(pm,false,sizeof(pm));memset(head,NULL,sizeof(head));for(int i=1;i<=m;i++){scanf("%d",&a);pm[a]=true; //標記能夠攻擊的點}for(int i=1;i<n;i++){scanf("%d%d",&aa,&b);add(aa,b);add(b,aa);}ans=0;if(pm[1]) //如果是給定的m中點，從父親過來的為0{dfs1(-1,1);dfs2(-1,1,0);}else //如果不是給定的m中的點，從父親過來的為-INF{dfs1(-1,1);dfs2(-1,1,-INF);}// dfs1(-1,a);/* for(int i=1;i<=n;i++)printf("i:%d %d pre:%d\n",i,node[i].max1,node[i].pre);*/// dfs2(-1,a,0); //最后一個參數表示從父親過來的最大距離，//注意不能從任意一點開始，因為從該點的父親過來的不為0，為-INF.printf("%d\n",ans);}return 0;
}
/*
10 1 0
3
10 1
1 3
8 3
3 5
5 7
5 4
2 4
9 4
6 4
*/

?

?

?