題目鏈接：

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

題目大意：

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

解題思路：

樹形dp.

有兩種方法可以解：

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

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

樹很靈活，遞歸很強(qiáng)大。多做些樹上的題。

代碼：

?

#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; //只用保存在子樹中，該點到給定點的最大距離、次大距離以及最大距離的直接兒子編號//向下推進(jìn)的時候，維護(hù)一個從父親到達(dá)該點的最大值 }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; //標(biāo)記能夠攻擊的點}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); //最后一個參數(shù)表示從父親過來的最大距離，//注意不能從任意一點開始，因為從該點的父親過來的不為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 */

?

?

?

總結(jié)

以上是生活随笔為你收集整理的树形dp-CF-337D. Book of Evil的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。