树形dp-CF-337D. Book of Evil-白红宇

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

阅读量：5949 次

发布时间：2019-06-19

本文共 2170 字，大约阅读时间需要 7 分钟。

题目链接：

题目大意：

给一棵树，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
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #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; else node[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); else dfs2(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

转载地址：http://tzsxx.baihongyu.com/

你可能感兴趣的文章