树形dp - CSDN
精华内容
参与话题
  • 树形动态规划(树形DP)入门问题—初探 & 训练

    万次阅读 多人点赞 2015-04-29 22:40:47
    树形DP入门 poj 2342 Anniversary party 先来个题入门一下~ 题意: 某公司要举办一次晚会,但是为了使得晚会的气氛更加活跃,每个参加晚会的人都不希望在晚会中见到他的直接上司,现在已知每个人的活跃指数和上司...

    树形DP入门

    poj 2342 Anniversary party   先来个题入门一下~
    题意:
    某公司要举办一次晚会,但是为了使得晚会的气氛更加活跃,每个参加晚会的人都不希望在晚会中见到他的直接上司,现在已知每个人的活跃指数和上司关系(当然不可能存在环),求邀请哪些人(多少人)来能使得晚会的总活跃指数最大。

    解题思路:
    任何一个点的取舍可以看作一种决策,那么状态就是在某个点取的时候或者不取的时候,以他为根的子树能有的最大活跃总值。分别可以用f[i,1]和f[i,0]表示第i个人来和不来。
    当i来的时候,dp[i][1] += dp[j][0];//j为i的下属
    当i不来的时候,dp[i][0] +=max(dp[j][1],dp[j][0]);//j为i的下属
    #include<iostream>
    #include<cmath>
    #include<algorithm>
    #include<vector>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<string>
    
    using namespace std;
    
    #define maxn 6005
    
    int n;
    int dp[maxn][2],father[maxn];//dp[i][0]0表示不去,dp[i][1]1表示去了
    bool visited[maxn];
    
    void tree_dp(int node)
    {
        int i;
        visited[node] = 1;
        for(i=1; i<=n; i++)
        {
            if(!visited[i]&&father[i] == node)//i为下属
            {
                tree_dp(i);//递归调用孩子结点,从叶子结点开始dp
                //关键
                dp[node][1] += dp[i][0];//上司来,下属不来
                dp[node][0] +=max(dp[i][1],dp[i][0]);//上司不来,下属来、不来
            }
        }
    }
    
    int main()
    {
        int i;
        int f,c,root;
        while(scanf("%d",&n)!=EOF)
        {
            memset(dp,0,sizeof(dp));
            memset(father,0,sizeof(father));
            memset(visited,0,sizeof(visited));
            for(i=1; i<=n; i++)
            {
                scanf("%d",&dp[i][1]);
            }
            root = 0;//记录父结点
            bool beg = 1;
            while (scanf("%d %d",&c,&f),c||f)
            {
                father[c] = f;
                if( root == c || beg )
                {
                    root = f;
                }
            }
            while(father[root])//查找父结点
                root=father[root];
            tree_dp(root);
            int imax=max(dp[root][0],dp[root][1]);
            printf("%d\n",imax);
        }
        return 0;
    }

     dp专辑 A - Rebuilding Roads [ 树形dp]

    第二道树形dp的题,看别人的代码,看了一下午才明白,还没入门呀~
    题意:
    有n个点组成一棵树,问至少要删除多少条边才能获得一棵有p个结点的子树?

    思路:
    设dp[i][k]为以i为根,生成节点数为k的子树,所需剪掉的边数。
    dp[i][1] = total(i.son) + 1,即剪掉与所有儿子(total(i.son))的边,还要剪掉与其父亲(+1)的边。
    dp[i][k] = min(dp[i][k],dp[i][j - k] + dp[i.son][k] - 2),即由i.son生成一个节点数为k的子树,再由i生成其他j-k个节点数的子树。
    这里要还原i与i.son和其父亲的边所以-2。
    大牛动态转移方程
    dp[root][j] = min(dp[root][j], dp[root][j - k] + dp[tree[root][i]][k] - 2);  
    中的-2,始终想不明白,不是-1就可以了吗?在这里纠结了好久,后来结合
    for (int i = 1; i <= n; i++)
        {
            //为以i为根,生成节点数为1的子树所需剪掉的边数  每个结点都有个父结点 +1  根结点有个虚拟的父结点,方便统一处理
            dp[i][1] = tree[i].size() + 1;
            for (int j = 2; j <= p; j++)
                dp[i][j] = MAX;
        }
    dp[root][p]--;
    才明白了,顿感大牛们智商太高了,膜拜一会儿~后来仔细想想,这样也是为了方便处理问题~
    #include<iostream>
    #include<cmath>
    #include<algorithm>
    #include<vector>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<string>
    using namespace std;
    
    const int MAX = 10000;
    
    vector <int> tree[160];
    //设dp[i][k]为以i为根,生成节点数为k的子树  所需 剪掉 的 边数
    int a, b, n, p, dp[160][160];
    bool son[160];
    
    void dfs(int root)
    {
        int len=tree[root].size();
        for (int i = 0; i < len; i++)
        {
            dfs(tree[root][i]);//递归调用孩子结点(后根遍历)
            for (int j = p; j > 1; j--)//j==1 的情况已经存在 >1 即可
                for (int k = 1; k < j; k++)
                    dp[root][j] = min(dp[root][j], dp[root][j - k] + dp[tree[root][i]][k] - 2);
        }
    }
    
    int main()
    {
        scanf("%d %d",&n,&p);
        memset(son, false, sizeof(son));
        for (int i = 0; i < n - 1; i++)
        {
            scanf("%d %d",&a,&b);
            tree[a].push_back(b);
            son[b] = true;//记录b是否有儿子
        }
        int root = 1;
        while(son[root])//找父结点
            root++;
        for (int i = 1; i <= n; i++)
        {
            //为以i为根,生成节点数为1的子树所需剪掉的边数  每个结点都有个父结点 +1  根结点有个虚拟的父结点,方便统一处理
            dp[i][1] = tree[i].size() + 1;
            for (int j = 2; j <= p; j++)
                dp[i][j] = MAX;
        }
        dfs(root);
        dp[root][p]--;// 与dp方程中+2有关,还原i与其父亲的边,最后i为父节点,则-1
        int ans = MAX;
        for (int i = 1; i <= n; i++)
            ans = min(ans, dp[i][p]);
        printf("%d\n",ans);
        return 0;
    }

    hdu 1520(我的第一道树形DP,附详细的讲解)

    关于树形DP,我这今天早上才弄懂了一道题。之前一直觉得这是什么特别高端的东西,但是就这道题而言,无非就是一个数塔的操作放在树上了

    题目大意:
    学校要开一个聚会。学校的教职工之间有上下级关系,为了让所有人开心,宴会组织者决定不会同时邀请一个人和他的上级(这让我想起我们昨天晚上聚餐李晔老师不来,她怕她来了我们放不开。。。。),对于每一个人,他能给聚会带来的欢乐度有一个值,问组织者该邀请哪些人能够使宴会的欢乐度达到最大值。
    解题思路:
    首先是DP的部分(也是很无聊的一部分):每个参与者都有两种状态,一种是参加,一种是不参加。这个状态的后续影响就是如果他参加了,他的直接上司和直接下属都不能参加。我们可以用一个二维二态的数组来描述:dp[i][1]表示第i个参与者参加了,dp[i][0]表示第i个参与者没有参加状态转移方程就是dp[i][1]=dp[i][1]+dp[i-1][0],dp[i][0]=dp[i][0]+Max(dp[i-1][0],dp[i-1][1])这要是放在一个线性表上,同志们肯定都直接呵呵了。可所谓的树形DP就是把这个简单的操作放在树上了。

    树的部分:
    之前很多大牛说图论的题目,难就难在一个建图。对这道题来说,DP是入门级的,很简单。但是这个建图让我纠结了许久。。。代码中是用静态链表的操作完成了一个父节点下面所有子节点的记录,对于一个子节点的操作完成之后,通过point[now].next指向下一个子节点,一直到point[now].next等于-1的时候,表示这个父节点下面所有的子节点已经遍历完成。返回父节点,再去操作这个父节点的兄弟节点。在这一点上,就是很直白的深搜的操作了。

    理解代码的时候,个人建议把图画出来,再跟踪代码的数据,逐个去记录。反正我就是这么理解的。。。。。
    #include<stdio.h>
    #include<string.h>
    #define N 6005
    
    struct node
    {
        int pa,son;
        int next;
    }point[N];
    //其实从这个结构体就可以看出很多东西,这就是一个静态链表,在计算过程中遍历一个节点的所有子节点的操作也是和链表完全相同的。
    //不过我这都是后知后觉啊。
    
    int dp[N][2],list[N],flag[N],value[N];
    int pos;
    int Max(int x,int y)
    {
        return x>y?x:y;
    }
    void add(int pa,int son)
    {
        point[pos].pa=pa;
        point[pos].son=son;
        point[pos].next=list[pa];  //以静态链表的形式存储一个父节点下面所有的子节点。
        list[pa]=pos++;
        return ;
    }
    void dfs(int root)   //这道题说起来是树形DP,但是最没有讲的价值的就是这个DP。就是个入门级数塔的操作放在树上了。
    {
        if(list[root]==-1)
        {
            dp[root][1]=value[root];
            dp[root][0]=0;
            return ;
        }
        int now=list[root];
        dp[root][0]=0;
        dp[root][1]=value[root];
        while(now!=-1)
        {
            dfs(point[now].son);
            dp[root][1]+=dp[point[now].son][0];  //既然取了父节点的值,子节点的值就不能再取了。
            
            //父节点的值没有取,子节点的值分取和不取两种情况,取其中较大的那种情况。
            dp[root][0]+=Max(dp[point[now].son][1],dp[point[now].son][0]); 
            
            now=point[now].next;//这个子节点计算过了,就要开始计算下一个子节点了。
        }
        return ;
    }
    
    int main()
    {
        int i,n;
        while(scanf("%d",&n)!=EOF)
        {
            for(i=1;i<=n;i++)
                scanf("%d",&value[i]);//记录每一个点的值
            int a,b;
            pos=0;
            memset(list,-1,sizeof(list));
            memset(flag,0,sizeof(flag));
            while(scanf("%d%d",&a,&b),a+b)
            {
                add(b,a);    //将边加入树中
                flag[a]=1;   //记录a有父节点,不可能是祖节点。
            }
            a=1;
            while(flag[a]==1)
                a++;     //从a往后查,遇到的第一个flag[a]的值是-1的点,这就是大名鼎鼎的祖节点了。
            dfs(a);
            printf("%d\n",Max(dp[a][0],dp[a][1]));
        }
        return 0;
    }

    POJ1192 树形DP 最优连通子集

    Description
           众所周知,我们可以通过直角坐标系把平面上的任何一个点P用一个有序数对(x, y)来唯一表示,如果x, y都是整数,我们就把点P称为整点,否则点P称为非整点。我们把平面上所有整点构成的集合记为W。 定义1 两个整点P1(x1, y1), P2(x2, y2),若|x1-x2| + |y1-y2| = 1,则称P1, P2相邻,记作P1~P2,否则称P1, P2不相邻。 定义 2 设点集S是W的一个有限子集,即S = {P1, P2,..., Pn}(n >= 1),其中Pi(1 <= i <= n)属于W,我们把S称为整点集。 定义 3 设S是一个整点集,若点R, T属于S,且存在一个有限的点序列Q1, Q2, ?, Qk满足: 1. Qi属于S(1 <= i <= k); 2. Q1 = R, Qk = T; 3. Qi~Qi + 1(1 <= i <= k-1),即Qi与Qi + 1相邻; 4. 对于任何1 <= i < j <= k有Qi ≠ Qj; 
    我们则称点R与点T在整点集S上连通,把点序列Q1, Q2,..., Qk称为整点集S中连接点R与点T的一条道路。 定义4 若整点集V满足:对于V中的任何两个整点,V中有且仅有一条连接这两点的道路,则V称为单整点集。 定义5 对于平面上的每一个整点,我们可以赋予它一个整数,作为该点的权,于是我们把一个整点集中所有点的权的总和称为该整点集的权和。 
    我们希望对于给定的一个单整点集V,求出一个V的最优连通子集B,满足: 1. B是V的子集 2. 对于B中的任何两个整点,在B中连通; 
    3. B是满足条件(1)和(2)的所有整点集中权和最大的。
    Input
    第1行是一个整数N(2 <= N <= 1000),表示单整点集V中点的个数; 
    以下N行中,第i行(1 <= i <= N)有三个整数,Xi, Yi, Ci依次表示第i个点的横坐标,纵坐标和权。同一行相邻两数之间用一个空格分隔。-10^6 <= Xi, Yi <= 10^6;-100 <= Ci <= 100。
    Output
    仅一个整数,表示所求最优连通集的权和。
    Sample Input
    5
    0 0 -2
    0 1 1
    1 0 1
    0 -1 1
    -1 0 1
    Sample Output
    2
    题目很繁琐,该题大意为:
    给定一个平面整点集,点与点间在|x1-x2| + |y1-y2| = 1时相邻,且形成的图没有回路, 每个点有一个可正可负的权值,求最大权和连通子图。 
    解题思路一:
    /*
    给定的是一颗树,根据题意,我们可以从任意一个节点出发,必能访问到其他所有节点,那么dp的起点可以在任意一个节点。
    我们从该起点出发,对以此点为根的树的每个分支进行搜索,采用树的后续遍历法则,对于每个子树来说,dp值首先加上根节点
    (因为要保证连通性,所以返回值中必须包含根节点的值,即使为负数也必须加上)先对每个分支dp,然后看分支dp的返回值是不是正数,
    如果是正数,那么我们就把该分支的返回值加入到该树中去。
    就是每个子树的根节点(包括叶子节点)记录dp[i][0]与dp[i][1],前一个表示不包含根的最大值,后一个表示包含根的最大值。
    那么我们可以得到对于dp[i][0],必然是所有分支中dp[child][0]与dp[child][1]中大于0的最大值的累加
    (因为不包含树根,所以在根节点上的连通性不用保证),
    dp[i][1]必然是所有分支中dp[child][1]中大于0的最大值的累加再加上该树根本身的值(因为要保证连通性)。
    最后只要比较dp[root][0]与dp[root][1],输出较大。
    */
    #include <stdio.h>
    #include <iostream>
    using namespace std;
    int Abs(int x)
    {
        return x>=0?x:-x;
    }
    int max(int x,int y,int z)
    {
        if(x<y) x=y;
        if(x<z) x=z;
        return x;
    }
    int max(int x,int y)
    {
        return x>y?x:y;
    }
    struct P
    {
        int x,y,c;
        void input()
        {
            scanf("%d%d%d",&x,&y,&c);
        }
        bool isConnect(P & t)
        {
            if(Abs(x-t.x)+Abs(y-t.y)==1) return 1;
            return 0;
        }
    }p[1005];
    struct Edge
    {
        int v,next;
    }edge[10005];
    int edgeNum,head[1005];
    int dp[1005][2];
    void addEdge(int u,int v)
    {
        edge[edgeNum].v=v;
        edge[edgeNum].next=head[u];
        head[u]=edgeNum++;
    }
    void dfs(int x,int father)
    {
        dp[x][0]=0;
        dp[x][1]=p[x].c;
        for(int i=head[x];i!=-1;i=edge[i].next)
        {
            if(edge[i].v!=father)
            {
                dfs(edge[i].v,x);
                dp[x][0]=max(dp[x][0],dp[edge[i].v][0],dp[edge[i].v][1]);
                if(dp[edge[i].v][1]>0)
                {
                    dp[x][1]+=dp[edge[i].v][1];
                }
            }
        }
    }
    int main()
    {
        int n;
        while(scanf("%d",&n)!=EOF)
        {
            for(int i=0;i<n;i++)
            {
                head[i]=-1;
                p[i].input();
            }
            edgeNum=0;
            for(int i=0;i<n;i++)
              for(int j=i+1;j<n;j++)
              {
                  if(p[i].isConnect(p[j]))
                  {
                      addEdge(i,j);
                      addEdge(j,i);
                  }
              }
            dfs(0,-1);
            printf("%d\n",max(dp[0][0],dp[0][1]));
        }
    }
    解题思路2:
    //poj 1192 最优连通子集 (树型DP)
    /*
    题意:给定一个平面整点集,点与点间在|x1-x2| + |y1-y2| = 1时相邻,且形成的图没有回路,
          每个点有一个可正可负的权值,求最大权和连通子图。
    题解:树型DP,dp[i][0]表示以i为根的子树上不包括i的最大权和,dp[i][1]表示包括i的最大权和。
    */
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <vector>
    using namespace std;
    const int inf = 1<<28;
    int n,m;
    struct Point
    {
           int x,y,c;
    }p[1010];
    
    vector<int> con[1010];
    int dp[1010][2],mark[1010];
    
    void dfs(int v)
    {
         mark[v]=1;
         dp[v][0]=0,dp[v][1]=p[v].c;
         int j;
         for (int i=0;i<con[v].size();i++)
         if (!mark[con[v][i]])
         {
             j=con[v][i];
             dfs(j);
             dp[v][0]=max(dp[v][0],max(dp[j][0],dp[j][1]));
             if (dp[j][1]>0) dp[v][1]+=dp[j][1];
         }
    }
    
    int main()
    {
        scanf("%d",&n);
        for (int i=0;i<n;i++)
            scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].c);
        for (int i=0;i<n;i++)
        for (int j=i+1;j<n;j++)
        if (abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y)==1)
        {
              con[i].push_back(j);
              con[j].push_back(i);
        }
        dfs(0);
        printf("%d/n",max(dp[0][0],dp[0][1]));
    
        return 0;
    }
    
    解题思路3:
    /*
    这道题着实花了很长时间才搞明白,对图的知识忘得太多了,看这道题之前最好先把图的邻接表表示方法看下,
    有助于对这道题的理解,这道题让我对深度优先遍历又有了进一步的了解
    
    这道题最好画个图,有助于理解,不过你要是画个错误的图此题就无解了
    
    其实就是一个求无向树的所有子树和的最大值
    树形dp
    dp[i][0]表示以i为根,不包括i结点的子树获得最大权
    dp[i][1]表示以i为根,包括i结点的子树获得的最大权
    dp[i][0] = max(dp[k][0], dp[k][1]) k为i的所有孩子结点
    dp[i][1] = i结点的权 + dp[k][1] 如果dp[k][1] > 0
    */
    #include <stdio.h>
    #include <cstring>
    #include <stdlib.h>
    
    using namespace std;
    
    struct node    //这个名字起得不是很恰当,说是结点,其实是边,本题建的是有向边
    {
        int u;     //边所指向的结点
        int next;  //与改变共起点的边,和邻接表表示图的方法差不多,只不过这里用的是一个int型的变量而不是一个指针
    };
    
    struct Point
    {
        int x;
        int y;
        int c;
    };
    Point point[1015];
    int head[1015];     //head[1]是以1开头的边
    node edge[1015*10]; //表示边
    int visited[1015];
    int n;
    int count=0;
    int dp[1015][2];
    
    void init()
    {
        memset(head,-1,sizeof(head)); //把以任何一个点的开始的边都设置为一个无效的变量
    }
    
    void input()
    {
        int i;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d %d %d",&point[i].x,&point[i].y,&point[i].c);
        }
    }
    
    void addEdge(int c ,int d)
    {
        edge[count].u=d;         //这是一条有向边
        edge[count].next=head[c];
        head[c]=count++;
    
        edge[count].u=c;        //这是另一条有向边
        edge[count].next=head[d];
        head[d]=count++;
    }
    
    void buildTree()
    {
        int i,j;
        for(i=0;i<n;i++)
        {
            for(j=i+1;j<n;j++)
            {
                if((abs(point[i].x - point[j].x) + abs(point[i].y - point[j].y)) == 1)
                {
                    addEdge(i,j);    //添加一对有向边
                }
            }
        }
    }
    
    int max(int a,int b)
    {
        return a>b?a:b;
    }
    
    void dfs(int u)
    {
        visited[u]=1;
        dp[u][0]=0;
        dp[u][1]=point[u].c;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].u;
            if(visited[v]==0)
            {
                dfs(v);
    
                dp[u][0]=max(dp[u][0],max(dp[v][0],dp[v][1]));//注意权值有正有负,这个语句即更新dp[u][0]
                if(dp[v][1]>0)    //当改点不选时就没有必要更新,因为值为1,当选的时候要更新该点,因为父节点要用到子结点的值
                {
                	/*这个语句更新dp[u][i],更新的方法其实差不多,u是父节点,v是子节点,当选u节点时,要加上其儿子,
    				  若不选u节点时,比较自己和儿子节点
                	*/
                    dp[u][1]=dp[u][1]+dp[v][1];
                }
            }
        }
    }
    
    int main()
    {
        init();//初始化操作
        input();//解决输入问题
        buildTree();//构造树,采用邻接表的形式
        dfs(0);// 深度优先遍历
        printf("%d\n",max(dp[0][0],dp[0][1]));
        return 0;
    }

    hdu1561 树形DP The More The Better

    Problem Description
    ACboy很喜欢玩一种战略游戏,在一个地图上,有N座城堡,每座城堡都有一定的宝物,在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因,有些城堡不能直接攻克,要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮ACboy算出要获得尽量多的宝物应该攻克哪M个城堡吗?
     
    Input
    每个测试实例首先包括2个整数,N,M.(1 <= M <= N <= 200);在接下来的N行里,每行包括2个整数,a,b. 在第 i 行,a 代表要攻克第 i 个城堡必须先攻克第 a 个城堡,如果 a = 0 则代表可以直接攻克第 i 个城堡。b 代表第 i 个城堡的宝物数量, b >= 0。当N = 0, M = 0输入结束。
     
    Output
    对于每个测试实例,输出一个整数,代表ACboy攻克M个城堡所获得的最多宝物的数量。
    Sample Input
    3 2
    0 1
    0 2
    0 3
    7 4
    2 2
    0 1
    0 4
    2 1
    7 1
    7 6
    2 2
    0 0
    Sample Output
    5
    13
    思路:自己建立一个根root,使森林的根都成为root的孩子,然后树形dfs+简单背包

    0-1背包裸代码:
    for i=1..N
        for v=V..0
            f[v]=max{f[v],f[v-c[i]]+w[i]};

    状态转移方程:f[root][k]=max(f[root][k],f[root][k-j]+dp[u][j]);

    m是个数,j是存几个,f[i][j]表示的是以i为根攻克j个城堡(且这j个城堡必须是它子树上的,不包括它本身),dp[i][j]表示的是是以i为根攻克j个城堡(且这j个城堡必须是它子树上的,一定它本身,ans[i]表示每个城堡的宝物,所以一定有dp[i][1]=ans[i];)。
    for(int k=m;k>=0;k--)
          for(int j=0;j<=k;j++)
               f[root][k]=max(f[root][k],f[root][k-j]+dp[u][j]);

    更新f[root][0~m]数组,然后全部更新完之后更新dp[root][0~m]。
    如图所示样例,先从root即0点访问3,3没有孩子,执行更新dp操作,因为所以叶子都满足dp[i][0~m]=ans[i],所以dp[3][0~m]都等于ans[3],以下同理。

    返回到root,更新f[0][m~0]。
    访问root-->2-->7-->6,访问到叶子,更新dp[6][0~m]。返回7,更新f[7][m~0],
    从7-->5,更新叶子节点dp[5][0~m],
    从5-->7,再次更新f[7][m~0],
    从7-->2,更新dp[7][0~m],返回2节点,更新f[2][m~0],
    从2-->4,更新叶子节点dp[4][0~m],
    从4-->2,更新f[2][m~0],
    从2-->1,更新dp[1][0~m],
    从1-->2,更新f[2][m~0],
    从2-->root,更新dp[2][0~m],
    更新f[0][m~0],更新dp[0][0~m]。
    #include<stdio.h>
    #include<string.h>
    #define N 205
    int n,m,edgeNum=0;
    int ans[N],dp[N][N],f[N][N];
    int visit[N],head[N];
    struct Line{int v,next;}edge[N];
    int max(int a,int b){return a>b?a:b;}
    void add(int u,int v)
    {
        edge[edgeNum].v=v;
        edge[edgeNum].next=head[u];
        head[u]=edgeNum++;
    }
    void dfs(int root)
    {
        visit[root]=1;
        for(int i=head[root];i!=-1;i=edge[i].next)
        {
            int u=edge[i].v;
            if(!visit[u])
            {
                dfs(u);
                for(int k=m;k>=0;k--)
                  for(int j=0;j<=k;j++)
                  f[root][k]=max(f[root][k],f[root][k-j]+dp[u][j]);
            }
        }
        for(int i=1;i<=m+1;i++)
          dp[root][i]=f[root][i-1]+ans[root];
    }
    int main()
    {
        int a,b;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            if(n==0&&m==0) break;
            edgeNum=ans[0]=0;
            memset(f,0,sizeof(f));
            memset(dp,0,sizeof(dp));
            memset(head,-1,sizeof(head));
            memset(visit,0,sizeof(visit));
            for(int i=1;i<=n;i++)
            {
                scanf("%d%d",&a,&b);
                ans[i]=b;
                add(a,i);
            }
            dfs(0);
            printf("%d\n",dp[0][m+1]);
        }
    }

    树形 dp 初探

    树形 dp 就是在一颗树上做 dp ,其基本思想是由子节点的信息推出父节点的信息。
    由于树都是一般树,可能不只二叉,所以要用到一般树的“左儿子右兄弟”表示法(详见代码中的 first_child 和 next_sibling)。

    hdu 1520 Anniversary party

    最基本的树形 dp 。
    题目大意是,有一群人之间有上下级关系,在一个 party 中,有直接的上下级关系(即树中的父子关系)的人不能同时出席,每个人都有个 rating ,闻如何选择出席的人,使得所有人的 rating 之和最大。
    每个节点有两个值,表示这个节点及其子节点所能取得的最大 rating 。max_with 是选择此节点的情况,max_without 不选择此节点
    有状态转移方程:
    选择此节点的最大值 = 所有子节点不选择的最大值之和
    不选择此节点的最大值 = 每个子节点选择或者不选择的最大值之和

    mark:简单的树形dp题,从每个人的状态着手考虑,每个人要么参加,要么不参加,那么状态dp[i][0]代表参加,dp[i][1]代表不参加。
        dp[i][0] += dp[son][1];
        dp[i][1] += max(dp[son][1], dp[son][0]);
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    const int N = 6010;
    
    struct node {
    
        int v;
        node *next;
    }*head[N],tree[2*N];
    int n,m,ptr;
    int w[N],vst[N];
    int dp[N][2];
    
    int max(int a, int b) {return a > b ? a : b;}
    
    void init()
    {
        ptr = 1;
        memset(vst, 0, sizeof(vst));
        memset(dp, 0, sizeof(dp));
        memset(head, 0, sizeof(head));
    }
    
    void AddEdge(int x,int y)
    {
        tree[ptr].v = y;
        tree[ptr].next = head[x],head[x] = &tree[ptr++];
    }
    
    void dfs(int v)   //v代表父亲节点
    {
        vst[v] = 1;
        node *p = head[v];
        dp[v][0] = w[v];
        while (p != NULL)
        {
            if(vst[p->v]) {p = p->next; continue;}
            dfs(p->v);    //p->v代表v的儿子节点
            dp[v][0] += dp[p->v][1];
            dp[v][1] += max(dp[p->v][0], dp[p->v][1]);
            p = p->next;
        }
    }
    
    int main()
    {
        int i,j,k;
        while(~scanf("%d", &n))
        {
            init();
            for(i = 1; i <= n; i++)
                scanf("%d", w+i);
            while(scanf("%d%d", &j, &k), j+k)
            {
                AddEdge(j, k);
                AddEdge(k, j);
            }
            dfs(1);
            printf("%d\n", max(dp[1][0], dp[1][1]));
        }
    }

    展开全文
  • 树形dp整理及入门

    千次阅读 多人点赞 2020-08-14 22:44:12
    树形dp常用作解三种题: 1.最大独立子集 最大独立子集的定义是,对于一个树形结构,所有的孩子和他们的父亲存在排斥,也就是如果选取了某个节点,那么会导致不能选取这个节点的所有孩子节点。 询问是让你给出这颗...

    树形dp常用作解三种题:

    1.最大独立子集

    最大独立子集的定义是,对于一个树形结构,所有的孩子和他们的父亲存在排斥,也就是如果选取了某个节点,那么会导致不能选取这个节点的所有孩子节点,同样,它的父亲也不能被选择。

    一般询问是要求给出当前这颗树的最大独立子集的大小(被选择的节点个数)。

    思路:对于任意一个节点,他都有两种选择:

    A . 选择:选择当前节点Father,那么他的孩子必定不能被选择,此时对于N和N的孩子们来说,能构成的最大独立子集是

    Father.Yes=1//选择自身
    for(i=0;i<Father.sons.size();++i)
        Father.Yes+=Father.sons[i].No;

    B . 不选择:不选择当前节点Father,那么对于他的每一个孩子来说都可以选择要或者不要,此时对于N和N的孩子们来说,此时能构成的最大独立子集是

    for(i=0;i<Father.sons.size();++i)  
        Father.No+=max(Father.sons[i].No,Father.sons[i].Yes);

    当然可以在这基础上加以变化,比如给点设置权值,要求求得的这个最大独立子集是满足有最大权值和的。

     

    2.树的重心

    树的重心定义为,当将节点x去掉后,树所形成的各个联通块的节点个数最少。

    那么显而易见,我们需要对每一个节点维护两个值。一个是包含他在内的所有节点的个数【用来返回给他们的‘父亲’】,一个是这个点的最大子树所含有的节点个数。

    虽然说是一棵树,但其实本身应该作为无根树考虑,也就是,父亲并不是严格意义上的父亲,如下图:

    在考虑C的时候,我们应该把C当成整棵树的根,因此C有三棵子树,但是在真正实现的时候,这追踪方法下的复杂度是O(n^2)的,并不现实。时机上,根据树的性质我们可以先求出C在遍历时的孩子个数sum,往上走的分支只要用n-sum就得到了。我们要求的节点就是拥有最大子树的节点。

     

    3.树的直径

    树的直径定义为一棵树上两个节点间的路径长度的最大值。

    一般思路:一棵树上n个节点,两两配对可以组成n*(n-1)/2,所以我们可以对n个节点都做一次dfs,并求得最长的路径,这样这些配对必定会在dfs的过程中求出,这样复杂度就是O(n*n),n次遍历,每次都要遍历除了自己以外的n-1个节点。

    进阶思路:我们以任意一个节点作为根节点,得到他的最高子树的叶子节点,那么这个节点必定是其中的一个节点,在以这个点为起点,dfs得到和他最大距离的点,这条路就是最长路径,复杂度为O(n),两次dfs。

    树形dp:我们以任意一个点为根,向下进行遍历,而经过这个点的最大路径一定是在他的不同的子树中,因此我们可以记录这个点的各个子树的高度的最大值和次大值。累加即为经过这个节点时的最长路经长度。

    疑问:题目并没有限制一个节点只能往下找,同样可以往上找,那为什么不往上找呢。解答:往上找出来的路径必定会经过他的父亲,问题就由经过孩子的最大路径变成了经过父亲的最大路径,问题的本质是没有变的,因为这样找出来的路径,父亲和孩子是相同的,是同时经过父亲和孩子的,也就是同样的问题,那么这个问题归根到底就是经过根的最大路径,所以问题重复了,因此我们不必往上找。

     

    树形dp的实现:

    对于有根树,可以考虑建树递归,在回溯的时候更新结果。

    对于无根树,用vector实现邻接表存储。

    存储结构:

    A. 无权值

    vector<int>Picture[n+1];

    遍历方式为:

    void dp(int now,int pre){
        int len=Picture[now].size();
        for(int i=0;i<len;i++) {
            if(Picture[now][i]==pre)continue;//不能回父亲 否则递归不能结束  会吃尽内存导致程序崩溃抑或是爆栈等
            dp(Picture[now][i],now);
        }
    } 

     

    下面给出三种类型题目的代码:【注:下面的遍历方式都是默认树节点从1开始的,如从0开始将递归入口search(1,0)修改为search(0,-1)即可】

    1.最大独立子集

    #include<cstdio>
    #include<vector>
    #include<algorithm>
    using namespace std;
    vector<int>Node[1000005];
    int Maxsize,n;//最大独立子集大小 
    
    struct returnType{
        int come,notcome;
    };
    
    returnType search(int now,int pre){
        returnType fa,son; 
        int len=Node[now].size(),soncome,sonnotcome;
        fa.come=1;//总结点数先算上自身1 
        fa.notcome=0;//最大子树先设置为0 
        for(int i=0;i<len;i++){
            if(Node[now][i]==pre){continue;}//不回父亲
            son=search(Node[now][i],now);
            fa.come+=son.notcome;
            fa.notcome+=max(son.come,son.notcome);
        }
        return fa;
    }
    
    int main(){
        int u,v;
        scanf("%d",&n);
        for(int i=1;i<n;i++){
            scanf("%d%d",&u,&v);
            Node[u].push_back(v);
            Node[v].push_back(u);
        }
        returnType father=search(1,0);
        printf("%d",max(father.come,father.notcome));
        return 0;
    }
    

    2.树的重心

    #include<cstdio>
    #include<vector>
    #include<algorithm>
    using namespace std;
    int num[1000005],size[1000005],n;//num :节点数   size :最大子树的节点数
    vector<int>Node[1000005];
    int target,Maxsize;//重心与最大子树尺寸 
    
    void search(int now,int pre){
        int len=Node[now].size(),result,rest;
        num[now]=1;//总结点数先算上自身1 
        size[now]=0;//最大子树先设置为0 
        for(int i=0;i<len;i++){
            if(Node[now][i]==pre){continue;}//不回父亲
            search(Node[now][i],now);
               size[now]=max(size[now],num[Node[now][i]]);
            num[now]+=num[Node[now][i]]; 
        }
        rest=n-num[now];
        size[now]=max(size[now],rest);
           if(Maxsize<size[now]){
               Maxsize=size[now];
               target=now;
        }
    }
    
    int main(){
        int u,v;
        scanf("%d",&n);
        for(int i=1;i<n;i++){
            scanf("%d%d",&u,&v);
            Node[u].push_back(v);
            Node[v].push_back(u);
        }
        search(1,0);
        printf("%d",target);
        return 0;
    }

    哇,有没有感觉num和size数组是在太耗内存了。没关系,咱们有奇技淫巧。

    #include<cstdio>
    #include<vector>
    #include<algorithm>
    using namespace std;
    vector<int>Node[1000005];
    int n,target,Maxsize;//重心与最大子树尺寸 
    
    struct returnType{
        int size;
        int num;
    };
    
    returnType search(int now,int pre){
        returnType fa,son; 
        int len=Node[now].size(),result,rest;
        fa.num=1;//总结点数先算上自身1 
        fa.size=0;//最大子树先设置为0 
        for(int i=0;i<len;i++){
            if(Node[now][i]==pre){continue;}//不回父亲
            son=search(Node[now][i],now);
               fa.size=max(fa.size,son.num);
            fa.num=son.num; 
        }
        rest=n-fa.num;
        fa.size=max(fa.size,rest);
           if(Maxsize<fa.size){
               Maxsize=fa.size;
               target=now;
        }
        return fa;
    }
    
    int main(){
        int u,v;
        scanf("%d",&n);
        for(int i=1;i<n;i++){
            scanf("%d%d",&u,&v);
            Node[u].push_back(v);
            Node[v].push_back(u);
        }
        search(1,0);
        printf("%d",target);
        return 0;
    }

    其实对一个节点来说,只是需要它的孩子们的信息,所以并没有必要开个数组存下来所有的数据。

     

    3.树的直径

    #include<cstdio>
    #include<vector>
    #include<algorithm>
    using namespace std;
    int first[1000005],second[1000005];//树形dp求解最长路
    vector<int>Node[1000005];
    int longest;
    void search(int now,int pre){
        int len=Node[now].size(),result;
        for(int i=0;i<len;i++){
            if(Node[now][i]==pre)continue;//不回父亲
            search(Node[now][i],now);
            if(first[Node[now][i]]+1>first[now]){
                second[now]=first[now];
                first[now]=first[Node[now][i]]+1;
            }
            else if(first[Node[now][i]]+1>second[now]){
                second[now]=first[Node[now][i]]+1;
            }
        }
        longest=max(first[now]+second[now],longest);
    }
    
    int main(){
        int n,u,v;
        scanf("%d",&n);
        for(int i=1;i<n;i++){
            scanf("%d%d",&u,&v);
            Node[u].push_back(v);
            Node[v].push_back(u);
        }
        search(1,0);
        printf("%d",longest+1);
        return 0;
    }

     

    展开全文
  • 树形dp+树形结构总结

    万次阅读 多人点赞 2017-10-19 17:34:15
     最近写了好多树形dp+树形结构的题目,这些题目变化多样能与多种算法结合,但还是有好多规律可以找的。 树形dp一般都是用子树更新父亲(即从下向上更新),那么首先应该考虑的是一个一个子树的更新父亲还是把所有...

    总结

          最近写了好多树形dp+树形结构的题目,这些题目变化多样能与多种算法结合,但还是有好多规律可以找的。

    先说总的规律吧!

          一般来说树形dp在设状态转移方程时都可以用f[i][]表示i这颗子树怎么怎么样的最优解,实现时一般都是用子树更新父亲(即从下向上更新),那么首先应该考虑的是一个一个子树的更新父亲还是把所有子树都算完了在更新父亲?这就要因题而异了,一般来说有两种情况:1.需要把所有子树的信息都掌握之后再更新子树的就需要把所有子树都算完了在更新父亲。2.而像树上背包这样的问题就需要一个一个的更新,每次都用一个子树更新已经更新完的子树+父亲,最后就可以将这一部分的子树更新完了,再继续往上更新,最后根节点就是答案。

    其实上面的两种情况可以总结成一种情况就是一个个子树更新父亲,一般来说第一种情况应用更多,也能解决第二情况的问题,只不过如果符合第二种情况的时候用第二种可以速度更快一点,毕竟你省了一遍循环嘛。

     在分题型说说说说树形dp的规律!

     1.子树和计数。

    这类问题主要是统计子树和,通过加减一些子树满足题目中要求的某些性质。

    1.codeforces 767C Garland

     这道题是让你把树分成3部分,使每部分点权和相等,这就是通过算子树的size[]实现的。

    2.洛谷1122最大子树和

    这道题让你剪去一些子树,让剩下的子树点权和最大。这题就要维护子树的点权和,f[i]表示i这颗子树的点权和最大值。

    2.树上背包问题

    这类问题就是让你求在树上选一些点满足价值最大的问题,一般都可以设f[i][j]表示i这颗子树选j个点的最优解。

    1.洛谷1272重建道路

    这道题是让你剪去最少的边实现最后剩P个点。所以P个点就是背包,剪去的边数就是价值。这题需要转化一下把剪边变成加边。

    2.洛谷1273有线电视网

    这道题是让你在保证不亏损的情况下满足更多的客户看到转播。此时用户的个数就是容量,f[i][j]表示i这颗子树选j个用户能赚的最多的钱。

    3.花费最少的费用覆盖所有点

    这类问题是父亲与孩子有联系的题。基本有两种出法:1.选父亲必须不能选孩子(强制)2.选父亲可以不用选孩子(不强制)。
    1.洛谷2458 [SDOI2006]保安站岗
    这题就属于类型2.这就需要预估,要不要选这个节点的父亲。f[i][0]表示选自己,f[i][1]表示选孩子,f[i][2]表示选父亲。
    2.UVA 1220 Party at Hali-Bula(这是最大独立集问题,用做和上面题区分)  
    这题就是强制要求父亲和孩子不能同时选,但这题没有要求必须把所有点完全覆盖,只是让选尽可能多的点,所以这样就可以用f[i][0]表示选自己,f[i][1]表示选孩子,省去f[i][2]表示选父亲了,因为没有都覆盖的强制要求,他的父亲选不选可以到他父亲再判断。

    4.树上统计方案数问题

    这类问题就是给你一个条件,问你有多少个点的集合满足这样的条件。这类题主要运用乘法原理,控制一个点不动,看他能做多少贡献。

    1. 51nod1588幸运树。 问有多少个三元组满足幸运数字, 可以控制一个点不动,分成子树内,子树外两个部分,分别相乘就行了。可以看这个博客

    与多种算法结合&&大模拟

    这种题只能根据题目分析,然后随机应变了。

    1.洛谷3621 [APIO2007]风铃

    把题目中的要求变成公式就行了。

    2. 51nod1673树有几多愁

    这道题是非常强的综合题,用到了虚树+状压dp+树形dp,具体的看这个博客吧。

    3.51nod1531树上的博弈

    非常强的一道博弈题。需要分情况的讨论,还是具体的看这个博客吧。 

    下面具体分析这几到例题。

    1.codeforce 767C Garland

    2.洛谷1122最大子树和

    3.洛谷1272重建道路

    4.洛谷1273有线电视网

    5.洛谷2458 [SDOI2006]保安站岗

    6.洛谷3621 [APIO2007]风铃

    codeforce 767C Garland

    Once at New Year Dima had a dream in which he was presented a fairy garland. A garland is a set of lamps, some pairs of which are connected by wires. Dima remembered that each two lamps in the garland were connected directly or indirectly via some wires. Furthermore, the number of wires was exactly one less than the number of lamps.

    There was something unusual about the garland. Each lamp had its own brightness which depended on the temperature of the lamp. Temperatures could be positive, negative or zero. Dima has two friends, so he decided to share the garland with them. He wants to cut two different wires so that the garland breaks up into three parts. Each part of the garland should shine equally, i. e. the sums of lamps' temperatures should be equal in each of the parts. Of course, each of the parts should be non-empty, i. e. each part should contain at least one lamp.

    Help Dima to find a suitable way to cut the garland, or determine that this is impossible.

    While examining the garland, Dima lifted it up holding by one of the lamps. Thus, each of the lamps, except the one he is holding by, is now hanging on some wire. So, you should print two lamp ids as the answer which denote that Dima should cut the wires these lamps are hanging on. Of course, the lamp Dima is holding the garland by can't be included in the answer.

    Input

    The first line contains single integer n (3 ≤ n ≤ 106) — the number of lamps in the garland.

    Then n lines follow. Thei-th of them contain the information about thei-th lamp: the number lampai, it is hanging on (and0, if is there is no such lamp), and its temperatureti ( - 100 ≤ ti ≤ 100). The lamps are numbered from1 ton.

    Output

    If there is no solution, print -1.

    Otherwise print two integers — the indexes of the lamps which mean Dima should cut the wires they are hanging on. If there are multiple answers, print any of them.

    Examples

    Input

    62 40 54 22 11 14 2

    Output

    1 4

    Input

    62 40 64 22 11 14 2

    Output

    -1

    Note

    The garland and cuts scheme for the first example:


    题目大意把一颗树切成3部分,使得每一部分的点权和相等。

    题解

    很容易发现每一颗子树的点权是固定的,因为总和固定,设每一部分的大小为W,那么我们就从下往上更新,遇到等于W的子树就切一刀,sz重置成0,这就可以一边遍历子树,一边算sz.这题细节挺多的,需要注意一条链的情况和和三的倍数但不能分成几个相等的部分的情况。
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int N=1000100;
    int w[N],pre[N*2],last[N],other[N*2],num;
    inline void add(int x,int y){
    	num++;
    	pre[num]=last[x];
    	last[x]=num;
    	other[num]=y;
    }
    int n,root,sum,sz[N],cnt,ans[5];
    void dfs(int x,int fa){
    	sz[x]=w[x];
    	for(int i=last[x];i;i=pre[i]){
    		int v=other[i];
    		if(v!=fa){
    			dfs(v,x);
    			sz[x]+=sz[v];
    		}
    	}
    	//if(cnt==2) {system("pause");exit(0);}
    	if(sz[x]==sum) ans[++cnt]=x,sz[x]=0;
    }
    int main(){
    	int x,y;
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++){
    		scanf("%d%d",&x,&y);
    		if(x!=0) add(i,x),add(x,i);
    		else root=i;
    		w[i]=y;
    		sum+=y;
    	}
    	if(sum%3!=0){
    		puts("-1"); 
    	}
    	else{
    		sum/=3;
    		dfs(root,0);
    		//cout<<cnt<<endl;
    		if(cnt<=2) puts("-1"); //等于二说明是一条链,只有两部分。 
    		else printf("%d %d\n",ans[1],ans[2]);
    	}
    	return 0;
    }
    

    洛谷1122最大子树和

    题目描述

    小明对数学饱有兴趣,并且是个勤奋好学的学生,总是在课后留在教室向老师请教一些问题。一天他早晨骑车去上课,路上见到一个老伯正在修剪花花草草,顿时想到了一个有关修剪花卉的问题。于是当日课后,小明就向老师提出了这个问题:

    一株奇怪的花卉,上面共连有N 朵花,共有N-1条枝干将花儿连在一起,并且未修剪时每朵花都不是孤立的。每朵花都有一个“美丽指数”,该数越大说明这朵花越漂亮,也有“美丽指数”为负数的,说明这朵花看着都让人恶心。所谓“修剪”,意为:去掉其中的一条枝条,这样一株花就成了两株,扔掉其中一株。经过一系列“修剪“之后,还剩下最后一株花(也可能是一朵)。老师的任务就是:通过一系列“修剪”(也可以什么“修剪”都不进行),使剩下的那株(那朵)花卉上所有花朵的“美丽指数”之和最大。

    老师想了一会儿,给出了正解。小明见问题被轻易攻破,相当不爽,于是又拿来问你。

    输入输出格式

    输入格式:

    输入文件maxsum3.in的第一行一个整数N(1 ≤ N ≤ 16000)。表示原始的那株花卉上共N 朵花。

    第二行有N 个整数,第I个整数表示第I朵花的美丽指数。

    接下来N-1行每行两个整数a,b,表示存在一条连接第a 朵花和第b朵花的枝条。

    输出格式:

    输出文件maxsum3.out仅包括一个数,表示一系列“修剪”之后所能得到的“美丽指数”之和的最大值。保证绝对值不超过2147483647。

    输入输出样例

    输入样例#1:
    7
    -1 -1 -1 1 1 1 0
    1 4
    2 5
    3 6
    4 7
    5 7
    6 7
    
    输出样例#1:
    3

    说明

    【数据规模与约定】

    对于60%的数据,有N≤1000;

    对于100%的数据,有N≤16000。

    题解

    这题和上一题类似,都是求子树和。考虑如果子树的和为负,那么删掉它一定比不删掉它更优,用一个cut数组记录这个子树是否删去。注意这题不一定到根节点是最优的,所以要算一个子树更新一次。

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    #include<queue>
    using namespace std;
    int n;
    const int N=20010;
    int pre[N*2],last[N],other[N*2],num,dp[N],a[N],ans;
    bool cut[N];
    inline void add(int x,int y){
        num++;
        pre[num]=last[x];
        last[x]=num;
        other[num]=y;
    }
    void tree_dp(int x,int fa){
        dp[x]=a[x];
        for(int i=last[x];i;i=pre[i]){
            int v=other[i];
            if(v!=fa)
            tree_dp(v,x);
        }
        for(int i=last[x];i;i=pre[i]){
            int v=other[i];
            if(v!=fa&&!cut[v])
            dp[x]+=dp[v]; 
        }
        if(dp[x]<0) cut[x]=1;
        ans=max(ans,dp[x]);
    }
    int main(){
        int x,y;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
        tree_dp(1,1);
        
        printf("%d\n",ans);
        return 0;
    }

    洛谷1272重建道路

    题目描述

    一场可怕的地震后,人们用N个牲口棚(1≤N≤150,编号1..N)重建了农夫John的牧场。由于人们没有时间建设多余的道路,所以现在从一个牲口棚到另一个牲口棚的道路是惟一的。因此,牧场运输系统可以被构建成一棵树。John想要知道另一次地震会造成多严重的破坏。有些道路一旦被毁坏,就会使一棵含有P(1≤P≤N)个牲口棚的子树和剩余的牲口棚分离,John想知道这些道路的最小数目。

    输入输出格式

    输入格式:

    第1行:2个整数,N和P

    第2..N行:每行2个整数I和J,表示节点I是节点J的父节点。

    输出格式:

    单独一行,包含一旦被破坏将分离出恰含P个节点的子树的道路的最小数目。

    输入输出样例

    输入样例#1:
    11 6
    1 2
    1 3
    1 4
    1 5
    2 6
    2 7
    2 8
    4 9
    4 10
    4 11
    
    输出样例#1:
    2
    

    说明

    【样例解释】

    如果道路1-4和1-5被破坏,含有节点(1,2,3,6,7,8)的子树将被分离出来

    题解

    这题就有一些难度了,主要是要转化一些问题。

    我们发现这题意思就是删除一些边使原图剩P个节点,那么我们在进行树形dp的时候就要考虑这条是不是删,但这样就不太好转移。那么我们转化一下,假设把所有的边先都删除,那么我们要考虑这条边是不是要加进去,这要就好转移多了,就是一个裸地背包+树形dp。写的时候要判断是不是根节点。具体的转移方程写在代码里了。

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    const int inf=1e9+7;
    int n,p;
    const int N=200;
    int pre[N*2],last[N],other[N*2],num,ans=inf;
    int du[N],f[N][N];//f[i][j]表示在以i为根的子树里截取j个节点最少要删边数
    inline void add(int x,int y){
        num++;
        pre[num]=last[x];
        last[x]=num;
        other[num]=y;
    }
    void dfs(int x,int fa){
        f[x][1]=du[x]-(fa!=0);
        for(int i=last[x];i;i=pre[i]){
            int v=other[i];
            if(v!=fa){
                dfs(v,x);
                for(int j=p;j>=1;j--){
                    for(int k=1;k<j;k++)
                    f[x][j]=min(f[x][j],f[x][k]+f[v][j-k]-1);//为何要-1,因为一开始把所有的边都删了 
                }
            }
        }
        ans=min(ans,f[x][p]+(fa!=0));
    }
    int main(){
        int x,y;
        scanf("%d%d",&n,&p);
        for(int i=1;i<n;i++){
            scanf("%d%d",&x,&y);
            add(x,y);add(y,x);
            du[x]++;du[y]++;
        }
        memset(f,0x3f,sizeof(f) );
        dfs(1,0);
        printf("%d\n",ans);
        return 0;
    }

    洛谷1273有线电视网

    题目描述

    某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构,这棵树的根结点位于足球比赛的现场,树叶为各个用户终端,其他中转站为该树的内部节点。

    从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的,一场转播的总费用等于传输信号的费用总和。

    现在每个用户都准备了一笔费用想观看这场精彩的足球比赛,有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。

    写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。

    输入输出格式

    输入格式:

    输入文件的第一行包含两个用空格隔开的整数N和M,其中2≤N≤3000,1≤M≤N-1,N为整个有线电视网的结点总数,M为用户终端的数量。

    第一个转播站即树的根结点编号为1,其他的转播站编号为2到N-M,用户终端编号为N-M+1到N。

    接下来的N-M行每行表示—个转播站的数据,第i+1行表示第i个转播站的数据,其格式如下:

    K A1 C1 A2 C2 … Ak Ck

    K表示该转播站下接K个结点(转播站或用户),每个结点对应一对整数A与C,A表示结点编号,C表示从当前转播站传输信号到结点A的费用。最后一行依次表示所有用户为观看比赛而准备支付的钱数。

    输出格式:

    输出文件仅一行,包含一个整数,表示上述问题所要求的最大用户数。

    输入输出样例

    输入样例#1:
    5 3
    2 2 2 5 3
    2 3 2 4 3
    3 4 2
    输出样例#1:
    2
    

    说明

    样例解释

    如图所示,共有五个结点。结点①为根结点,即现场直播站,②为一个中转站,③④⑤为用户端,共M个,编号从N-M+1到N,他们为观看比赛分别准备的钱数为3、4、2,从结点①可以传送信号到结点②,费用为2,也可以传送信号到结点⑤,费用为3(第二行数据所示),从结点②可以传输信号到结点③,费用为2。也可传输信号到结点④,费用为3(第三行数据所示),如果要让所有用户(③④⑤)都能看上比赛,则信号传输的总费用为:

    2+3+2+3=10,大于用户愿意支付的总费用3+4+2=9,有线电视网就亏本了,而只让③④两个用户看比赛就不亏本了。

    题解

    典型的树形dp+01背包。

    f[i][j]表示i这个子树让j个用户转播所能赚的最多的钱。

    f[i][j]=max(f[i][j],f[v][k]+f[i][j-k]-w[i]).注意要倒序循环,否则可能一个点被重复用了多次。

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int n,m;
    const int N=3010;
    int pre[N*2],last[N],other[N*2],num,w[N*2],v[N];
    int f[N][N],size[N],du[N];
    inline void add(int x,int y,int z){
        num++;
        pre[num]=last[x];
        last[x]=num;
        other[num]=y;
        w[num]=z;
    }
    void work(int x,int fa){
        f[x][0]=0;
        for(int i=last[x];i;i=pre[i]){
            int v=other[i];
            if(v!=fa){
                work(v,x);
                size[x]+=size[v];
                /*for(int j=size[x];j>=0;j--)//刷表法 
                for(int k=size[v];k>=0;k--)
                f[x][j+k]=max(f[x][j+k],f[x][j]+f[v][k]-w[i]); 
                
                 size[x]+=size[v];*/
                 for(int j=size[x];j;j--)//填表法 必须倒序循环,否则会重复利用,如果压维就要倒序 
                 for(int k=1;k<=min(j,size[v]);k++)
                 f[x][j]=max(f[x][j],f[x][j-k]+f[v][k]-w[i]);//f[i][x][j]=f[i-1][x][j]+f[size[v]][v][k]-w[i];省去了第几个子树这一维 
            }
        }
        if(du[x]==1){
            f[x][1]=v[x];
            size[x]=1;
        }
    }
    int main(){
        int x,y,z;
        scanf("%d%d",&n,&m);
        memset(f,128,sizeof(f));
        for(int i=1;i<=n-m;i++){
            scanf("%d",&x);
            for(int j=1;j<=x;j++){
                scanf("%d%d",&y,&z);
                add(i,y,z);add(y,i,z);
                du[i]++;du[y]++;
            }
        }
        for(int i=n-m+1;i<=n;i++) scanf("%d",&v[i]);
        
        work(1,1);
    /*    for(int j=1;j<=n;j++)
        for(int i=1;i<=m;i++)
        printf("f[%d][%d]=%d\n",j,i,f[j][i]);*/
        for(int i=m;i>=0;i--){
            if(f[1][i]>=0){
                printf("%d\n",i);
                break;
            }
        }
        return 0;
    }

    洛谷2458 [SDOI2006]保安站岗

    题目描述

    五一来临,某地下超市为了便于疏通和指挥密集的人员和车辆,以免造成超市内的混乱和拥挤,准备临时从外单位调用部分保安来维持交通秩序。已知整个地下超市的所有通道呈一棵树的形状;某些通道之间可以互相望见。总经理要求所有通道的每个端点(树的顶点)都要有人全天候看守,在不同的通道端点安排保安所需的费用不同。

    一个保安一旦站在某个通道的其中一个端点,那么他除了能看守住他所站的那个端点,也能看到这个通道的另一个端点,所以一个保安可能同时能看守住多个端点(树的结点),因此没有必要在每个通道的端点都安排保安。

    编程任务:请你帮助超市经理策划安排,在能看守全部通道端点的前提下,使得花费的经费最少。

    输入输出格式

    输入格式:

    第1行 n,表示树中结点的数目。

    第2行至第n+1行,每行描述每个通道端点的信息,依次为:该结点标号i(0<i<=n),在该结点安置保安所需的经费k(<=10000),该边的儿子数m,接下来m个数,分别是这个节点的m个儿子的标号r1,r2,...,rm。

    对于一个n(0 < n <= 1500)个结点的树,结点标号在1到n之间,且标号不重复。

    输出格式:

    最少的经费。

    如右图的输入数据示例

    输出数据示例:

    输入输出样例

    输入样例#1:
    6
    1 30 3 2 3 4
    2 16 2 5 6
    3 5 0
    4 4 0
    5 11 0
    6 5 0
    输出样例#1:
    25

    说明

    样例说明:在结点2,3,4安置3个保安能看守所有的6个结点,需要的经费最小:25

    题解

    这题是父亲与孩子有限制的树形dp。

    由于这个点放不放保安与儿子放不放保安和父亲放不放保安都有关系,所以假设f[x][0] 自己选,f[x][1] 自己不选,儿子选,f[x][2] 自己不选,父亲选。dp不是没有后效性吗?为什么这个节点可以看他的父亲呢?其实是可以的,这个叫做未来计算,可以事先把还没发生但是肯定会发生的费用累加到答案中。那么这题就非常简单了。

    dp方程:f[x][0]+=min(f[vv][1],min(f[vv][2],f[vv][0]));f[x][2]+=min(f[vv][0],f[vv][1]);dp[x][1]有一些特殊的地方因为自己不选儿子并不一定所有的儿子都选,所以我们要选一个最优的儿子选。可以记一个f[vv][0]-f[vv][1]的最小值,最后把这个加进去就行了。

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    int n;
    const int N=2000; 
    const int inf=1e9;
    int pre[N*2],last[N],other[N*2],num;
    int f[N][5],v[N],du[N];//f[x][0] 自己选,f[x][1] 自己不选,儿子选,f[x][2] 自己不选,父亲选 
    inline void add(int x,int y){
        num++;
        pre[num]=last[x];
        last[x]=num;
        other[num]=y;
    }
    void dfs(int x,int fa){
        f[x][0]=v[x];//if(du[x]==1) f[x][0]=0;
        for(int i=last[x];i;i=pre[i]){
            int vv=other[i];
            if(vv!=fa){
                dfs(vv,x); 
            }
        }
        bool yes=0,have=0;int minn=inf;
        for(int i=last[x];i;i=pre[i]){
            int vv=other[i];have=true;
            f[x][0]+=min(f[vv][1],min(f[vv][2],f[vv][0]));
            f[x][2]+=min(f[vv][0],f[vv][1]);
            if(f[vv][0]<=f[vv][1]){
                f[x][1]+=f[vv][0];
                yes=1; 
            }
            else{
                f[x][1]+=f[vv][1];
                minn=min(minn,f[vv][0]-f[vv][1]);
            }
        }
        if(!yes) f[x][1]+=minn;
        if(!have) f[x][1]=inf;
    }
    int main(){
        int x,x1,y,z;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d%d%d",&x,&y,&z);
            v[x]=y;
            for(int i=1;i<=z;i++){
                scanf("%d",&x1);
                add(x,x1);add(x1,x);
            }
        }
        memset(f,0,sizeof(f));
        dfs(1,0);
        printf("%d\n",min(f[1][1],f[1][0]));
        return 0;
    }

    洛谷3621[APIO2007]风铃

    题目描述

    你准备给弟弟 Ike 买一件礼物,但是,Ike 挑选礼物的方式很特别:他只喜欢那些能被他排成有序形状的东西。

    你准备给 Ike 买一个风铃。风铃是一种多层的装饰品,一般挂在天花板上。

    每个风铃都包含一些由竖直线连起来的水平杆。每根杆的两头都有线连接,下面或者挂着另一根水平杆,或者挂着一个玩具。下面是一个风铃的例子:

    为了满足弟弟,你需要选一个满足下面两个条件的风铃:

    (1) 所有的玩具都在同一层(也就是说,每个玩具到天花板之间的杆的个数是一样的)或至多相差一层。

    (2) 对于两个相差一层的玩具,左边的玩具比右边的玩具要更靠下一点。

    风铃可以按照下面的规则重新排列:任选一根杆,将杆两头的线“交换”。也就是解开一根杆左右两头的线,然后将它们绑到杆的另一头。这个操作不会改变更下面的杆上线的排列顺序。

    正在训练信息学奥林匹克的你,决定设计一个算法,判断能否通过重新排列,将一个给定的风铃变为 Ike 喜欢的样子。

    考虑上面的例子,上图中的风铃满足条件(1),却不满足条件(2)——最左边的那个玩具比它右边的要高。

    但是,我们可以通过下面的步骤把这个风铃变成一个 Ike 喜欢的:

    1. 第一步,将杆 1 的左右两边交换,这使得杆 2 和杆 3 的位置互换,交换的结果如下图所示:

    2. 第二步,也是最后一步,将杆 2 的左右两边交换,这使得杆 4 到了左边,原来在左边的玩具到了右边,交换的结果发下图所示:

    现在的这个风铃就满足 Ike 的条件了。

    你的任务是:给定一个风铃的描述,求出最少需要多少次交换才能使这风铃满足 Ike 的条件(如果可能)

    输入输出格式

    输入格式:

    输入的第一行包含一个整数 n(1≤n≤100 000),表示风铃中有多少根杆。

    接下来的 n 行描述杆的连接信息。这部分的第 i 行包含两个由空格分隔的整数 li和 ri,描述杆 i 的左右两边悬挂的东西。如果挂的是一个玩具,则对应的值为-1,否则为挂在下面的杆的编号

    输出格式:

    输出仅包含一个整数。表示最少需要多少次交换能使风铃满足 Ike 的条件。如果不可能满足,输出-1。

    输入输出样例

    输入样例#1:
    6 
    2 3 
    -1 4 
    5 6 
    -1 -1 
    -1 -1 
    -1 -1 
    
    输出样例#1:
    2

    题解

    一个树形dp的变形。

    首先发现这个树一定是二叉树,根据邻接表的性质所以可以把左边的点最后加,这样边就是先左后右了。

    设mindep[i]表示i这个点的子树中铃的最小深度,maxdep[i]表示最大深度。dp[i]表示使i这颗子树变成满足条件的需要几步,转移就是两个子树相加就行了,需要注意的是不满足的情况,除了深度差大于1,还有这个条件不要丢掉。maxdep[c[1]]>mindep[c[2]]&&maxdep[c[2]]>mindep[c[1]]。

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    //#include<cmath>
    using namespace std;
    const int N=300010;
    int pre[N*2],last[N],other[N*2],num,w[N];
    int dep[N],mindep[N],maxdep[N],c[10],dp[N];
    inline void add(int x,int y){
        num++;
        pre[num]=last[x];
        last[x]=num;
        other[num]=y;
    }
    void dfs(int x,int fa){
        for(int i=last[x];i;i=pre[i]){
            int v=other[i];
            if(v!=fa){
                dep[v]=dep[x]+1;
                dfs(v,x);
                mindep[x]=min(mindep[x],mindep[v]);
                maxdep[x]=max(maxdep[x],maxdep[v]);
            }
        }
        if(w[x]==-1){
            mindep[x]=maxdep[x]=dep[x];
        }
        else{
            int cnt1=0;
            for(int i=last[x];i;i=pre[i]){
                int v=other[i];
                if(v!=fa)
                c[++cnt1]=v;
            }
            if((abs(maxdep[c[1]]-mindep[c[2]])>1)||(abs(mindep[c[1]]-maxdep[c[2]])>1) || (maxdep[c[1]]>mindep[c[2]]&&maxdep[c[2]]>mindep[c[1]])){
                puts("-1");exit(0);
            }
            dp[x]=dp[c[1]]+dp[c[2]]+((mindep[c[1]]<maxdep[c[2]])?1:0);
        }
    }
    void dfs1(int x,int fa){
        printf("%d ",x);
        for(int i=last[x];i;i=pre[i]){
            int v=other[i];
            if(v!=fa)
            dfs1(v,x);
        }
    }
    int main(){
        int n;
        int x,y;
        scanf("%d",&n);
        int cnt=n;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&x,&y);
            if(y==-1) y=++cnt,w[cnt]=-1;
            add(i,y);add(y,i);
            if(x==-1) x=++cnt,w[cnt]=-1;
            add(i,x);add(x,i);    
        }
        //cout<<other[last[2]]<<endl;
        memset(mindep,0x3f,sizeof(mindep));
        dfs(1,0);
        //if(maxdep[1]-mindep[1]>1) puts("-1"); 
        printf("%d\n",dp[1]);
        return 0;
    }
    


    展开全文
  • 【动态规划】树形dp

    2019-01-28 20:52:17
    概念理解: 我们学过的一般DP方程一般都是一...由于树本身的特殊性质,树的局部性体现在其递归结构上:即以一个节点为根的子树是由它儿子的子树组成的,所以我们在解决树形DP问题的时候一般是选择按照层数从底向上...

    概念理解:

    • 我们学过的一般DP方程一般都是一维或者二维的,而数组是一种线性结构,具有很强的位置关系限制(一个挨着一个),所以一般在线性结构上的dp都很容易计算

    • 然而除了线性的数据结构之外,还有很多非线性的数据结构,最典型的就是树。

    • 由于树本身的特殊性质,树的局部性体现在其递归结构上:即以一个节点为根的子树是由它儿子的子树组成的,所以我们在解决树形DP问题的时候一般是选择按照层数从底向上,也就是对于每个节点,用其它节点的子树答案计算出它的子树答案。

    特点解说:

    • 我们设置状态时也一般第一个是设置根,这样也可以用递归转移。

    • 因为树形dp是具有层次型的dp,所以我们实现dp时一般采用dfs递归更新,也就是信息界人称的“记忆化搜索”。

    • 树形dp因为是一张图,所以我们一般用邻接表或者vector来存储点与点之间的关系。

    例题:

    一、联合权值

    题目描述:
    无向连通图 G 有 n 个点,n−1 条边。点从 1 到 n 依次编号,编号为 i 的点的权值为 Wi,每条边的长度均为 1。图上两点 (u,v) 的距离定义为 u 点到 v 点的最短距离。对于图 G 上的点对 (u,v),若它们的距离为 2,则它们之间会产生Wv×Wu​ 的联合权值。
    请问图 G 上所有可产生联合权值的有序点对中,联合权值最大的是多少?所有联合权值之和是多少?


    输入输出格式

    输入格式:
    第一行包含 1 个整数 n。
    接下来 n−1 行,每行包含 2 个用空格隔开的正整数 u,v,表示编号为 u 和编号为 v 的点之间有边相连。
    最后 1 行,包含 n 个正整数,每两个正整数之间用一个空格隔开,其中第 i 个整数表示图 G 上编号为 i 的点的权值为 Wi。


    输出格式:
    输出共 1 行,包含 2 个整数,之间用一个空格隔开,依次为图 G 上联合权值的最大值和所有联合权值之和。由于所有联合权值之和可能很大,输出它时要对10007取余。


    分析:因为题目说两个点之间的距离为2就是一个有序数对,所以我们就可以知道一对有序序对之间必定隔着一个中转点 例如下图:
    在这里插入图片描述其中1、2、3、4互为序对,因为它们都隔着一个中转点5,它们之间的距离都为2,所以做这道题的基础就是枚举中转点,它延伸出去的点必定互为序对。

    那么枚举的问题解决了,这回我们就需要想算的问题。
    第一个求最大值很好理解,我们只需要枚举中间点,在枚举它延伸出去的点,然后找一个最大值和次大值就可以了。
    例如上图中的最大值就是 c*d=12;

    第二个问题需要用到乘法的一些定则。
    举个例子:
    上图的和为ab+ac+ad+ba+bc+bd+ca+cb+cd+da+dc+dba*b+a*c+a*d+b*a+b*c+b*d+c*a+c*b+c*d+d*a+d*c+d*b
    经过整理可以变成:
    ab+ac+ad+bc+bd+cd2(a*b+a*c+a*d+b*c+b*d+c*d)*2
    再经过整理可以变成:
    a(b+c+d)+b(c+d)+cd2(a*(b+c+d)+b*(c+d)+c*d)*2
    所以我们发现求和只需要用一个sum记录前几个数求得的和,然后不停的用后面的数累乘即可,具体的证明可以用乘法分配律展开求得。

    不过求得后最后的乘2不能忘掉,这也是一个坑点。

    那么具体代码如下:

    #include<bits/stdc++.h>
    using namespace std;
    #define P 10007
    struct node{
        int next,y;
    }e[1000001];
    int v[1000001];
    int n;
    int linkk[10000001];
    int len;
    void insert(int xx,int yy){
        e[++len].next=linkk[xx];
        linkk[xx]=len;
        e[len].y=yy;
    }
    int main(){
        scanf("%d",&n);
        for (int i=1,x,y;i<n;i++) scanf("%d %d",&x,&y),insert(x,y),insert(y,x);
        int ans=0,maxx=0;
        for (int i=1;i<=n;i++) scanf("%d",&v[i]);
        for (int i=1;i<=n;i++){
        	int max1=0,max2=0,sum=0;
    	    int t=linkk[i];
    	    for (int j=t;j;j=e[j].next){
    		    if (v[e[j].y]>max1) max2=max1,max1=v[e[j].y];
    		    else max2=max(max2,v[e[j].y]);
    		    ans=(ans+sum*v[e[j].y])%P;
    		    sum=(sum+v[e[j].y])%P;
    		}
    		maxx=max(maxx,max1*max2);
    	}
    	printf("%d %d",maxx,(ans*2)%P);
    	return 0;
    }
    

    大家别介意。。这道题的分析跟我写的博客一模一样。。不过我觉得我分析的还是挺到位的。(假的。)

    二、战略游戏

    题目描述:
    Bob喜欢玩电脑游戏,特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。他要建立一个古城堡,城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵,使得这些士兵能了望到所有的路。注意,某个士兵在一个结点上时,与该结点相连的所有边将都可以被了望到。
    请你编一程序,给定一树,帮Bob计算出他需要放置最少的士兵。


    输入格式
    输入文件中数据表示一棵树,描述如下: 第一行 N,表示树中结点的数目。 第二行至第N+1行,每行描述每个结点信息,依次为:该结点标号i,k(后面有k条边与结点I相连),接下来k个数,分别是每条边的另一个结点标号r1,r2,…,rk。 对于一个n(0<n<=1500)个结点的树,结点标号在0到n-1之间,在输入文件中每条边只出现一次。


    输出格式
    输出文件仅包含一个数,为所求的最少的士兵数目。


    分析:这是一道经典的树形dp问题。我们设:
    dp[i][0]dp[i][0]表示以i为根的子树的所有节点都能被瞭望到,第i个位置不放士兵的最小值
    dp[i][1]dp[i][1]表示以i为根的子树的所有节点都能被瞭望到,第i个位置放士兵的最小值

    不难发现,如果dp[i][0]不放士兵,那么它的儿子必定是要放士兵的,只有这样才能满足所有的东西都被瞭望到。
    转移方程如下:

    json(i) dp[i][0]+=dp[j][1]\sum_{j\in son(i)}\ dp[i][0]+=dp[j][1]

    如果第i个点放士兵,那么它的儿子节点士兵可放可不放,两个取一个较小值即可

    转移方程如下:
    json(i) dp[i][1]+=min(dp[j][0],dp[j][1])+1\sum_{j\in son(i)}\ dp[i][1]+=min(dp[j][0],dp[j][1])+1

    具体操作需要在图上完成,只需要开一个vector建立图然后在递归完成转移即可。

    那么具体代码如下:

    #include<bits/stdc++.h>
    using namespace std;
    int dp[2001][2];
    vector < int > e[1000011];
    int n;
    int vis[1100001];
    void Dp(int x){
        dp[x][0]=0;
        dp[x][1]=1;
        for (int i=0;i<e[x].size();i++){
    	    int y=e[x][i];
    	    Dp(y);
    	    dp[x][0]+=dp[y][1];
    	    dp[x][1]+=min(dp[y][0],dp[y][1]);
    	}
    }
    int main(){
        scanf("%d",&n);
        for (int i=1;i<=n;i++){
    	    int x,m;
    	    scanf("%d %d",&x,&m);
    	    for (int j=1,y;j<=m;j++) scanf("%d",&y),vis[y]=1,e[x].push_back(y)/*,e[y].push_back(x)*/;
    	}
    	int rot;
    	for (int i=0;i<n;i++) if (!vis[i]){
    	    rot=i;break;
    	}
    	Dp(rot);
    	printf("%d",min(dp[rot][0],dp[rot][1]));
    	fclose(stdin);
    	fclose(stdout);
    	return 0;
    }
    

    三、最大利润

    题目描述: 政府邀请了你在火车站开饭店,但不允许同时在两个相连接的火车站开。
    任意两个火车站有且只有一条路径,每个火车站最多有50个和它相连接的火车站。
    告诉你每个火车站的利润,问你可以获得的最大利润为多少。


    输入格式
    第一行输入整数N(<=100000),表示有N个火车站,分别用1,2。。。,N来编号。
    接下来N行,每行一个整数表示每个站点的利润,接下来N-1行描述火车站网络,每行两个整数,表示相连接的两个站点。


    输出格式
    输出一个整数表示可以获得的最大利润。


    分析:这题就是战略游戏的一个加权版。我们只要将战略游戏的+1改为+它的利润就可以了。不过需要注意的是因为一个地方被建立了商店之后与他相邻的商店都不能建立,所以只需要将转移方程稍微修改一下就可以了

    那么具体代码如下:

    #include<bits/stdc++.h>
    using namespace std;
    int v[1000001];
    vector < int > e[1000001];
    int n;
    bool vis[1000001];
    int dp[1000001][2];
    void Dp(int x){
    	vis[x]=1;
        dp[x][0]=0;
        dp[x][1]=v[x];
        for (int i=0;i<e[x].size();i++){
    	    int y=e[x][i];
    	    if (vis[y]) continue;
    	    Dp(y);
    	    dp[x][0]+=max(dp[y][1],dp[y][0]);
    	    dp[x][1]+=dp[y][0];
    	}
    }
    int main(){
    	freopen("profit.in","r",stdin);
    	freopen("profit.out","w",stdout);
        scanf("%d",&n);
        for (int i=1;i<=n;i++)scanf("%d",&v[i]);
        for (int i=1,x,y;i<n;i++) scanf("%d %d",&x,&y),e[x].push_back(y),e[y].push_back(x);
    	Dp(1);
    	printf("%d",max(dp[1][0],dp[1][1]));
    	fclose(stdin);
    	fclose(stdout);
    	return 0;
    } 
    

    如果你们想写状压,请去这里
    如果你们有兴趣去看我的其它博客,请看这里

    展开全文
  • 树形dp模板(C++版)

    2018-10-27 21:05:11
    最简单的树形dp入门,树上的最大点权独立集 #include &lt;cstdio&gt; #include &lt;algorithm&gt; #include &lt;cstring&gt; using namespace std; const int N=6e3+50; const int M=2e4+50...
  • 树形DP简单总结

    千次阅读 2018-07-14 15:52:16
    无向图没有环树形DP由于树有着天然的递归结构 父子结构 而且它作为一种特殊的图 可以描述许多复杂的信息 因此在树就成了一种很适合DP的框架问题:给你一棵树 要求用最少的代价(最大的收益)完成给定的操作树形DP ...
  • 树形DP

    2018-08-03 18:45:28
    知识点系列之---树形DP
  • 树形DP总结,持续更新
  • 树形dp总结

    2018-12-06 17:48:50
    1 与其他dp的不同点和相同点 我们先从最简单的01背包问题说起: for(int i=1;i&...很清晰,就是两个for循环对吧,但是树形dp的基本操作就是将一个结点所有子树的信息合到这个节点上,我们的for循...
  • 暂时看的一个比较好地讲解树形DP的课件,对初步了解树形DP有帮助
  • 动态规划--树形DP

    千次阅读 2018-03-28 16:37:28
    动态规划--树形DP 1、什么是树型动态规划 顾名思义,树型动态规划就是在“树”的数据结构上的动态规划,平时作的动态规划都是线性的或者是建立在图上的,线性的动态规划有二种方向既向前和向后,相应的线性的动态...
  • 树形DP总结

    2016-07-22 10:55:48
    题型一Q:给出一颗,每个节点有其价值,如果父节点在,子节点就不能存在,然后求选哪些点能得到最大价值。A:从问题入手,先得出dp[i][j] 表示第i个节点,状态为j (0:不选,1:选)的情况下的价值。 然后再推导...
  • 树形dp

    千次阅读 2011-03-20 10:33:00
    <br />poj 2057 虽然是树形dp 题目描述:现在你在树根上,你的房子在任意一个叶子上面,然后你要找遍所有的叶子取找你的房子,没选择一条路,你必须走到叶子或者树的分支上面可能有一些毛毛虫,他们可以...
  • 树形dp小结1

    千次阅读 2018-08-06 23:22:23
    解决这两类问题首先要确定父亲节点和子节点的关系,加入选了父亲节点就不能选子节点,那么在dp的时候,就要分两种情况来讨论,每个节点选还是不选,一般需要开一个二位数组dp[i][0],dp[i][1]分别代表这个节点选或是...
  • 树形DP一般解题思路

    2020-06-02 11:23:00
    树形DP 定义 整个题目给出,是一棵树。 一般而言:以节点从深到浅(子树从小到大)的顺序作为dp的阶段;dp状态表示中,第一维通常是节点的编号(代表以该节点为根的子树。)大多数时候,采用递归的方式实现树形dp。...
  • 树形DP的背包问题

    2019-05-18 23:43:20
    树形DP有一类问题是关于选择节点:我们可以用dp[i][0]表示不选,dp[i][1]表示可选可不选。 这里我们讨论的是树形dp的背包问题,也就是对节点个数限制,同时要求尽可能的价值极值。 我们考虑这样的动态规划方程: dp...
  • 树形dp模板(Java版)

    2018-10-27 21:33:10
    最简单的树形dp,树上最大点权独立集 import java.util.Scanner; public class Main{ static class Edge{ int v,next; Edge(int v,int next){ this.v=v; this.next=next; } ...
  • 树形DP总结(转)

    千次阅读 2013-07-29 19:48:29
    树,一种十分优美的数据结构,因为它本身就具有的递归性,所以... 枚举那么多种数据结构只是想说树方面的内容相当多,本专辑只针对在树上的动态规划,即树形DP.做树形DP一般步骤是先将树转换为有根树,然后在树上进行
  • 树形dp换根

    2019-09-19 17:00:24
    换根解决的是“不定根”的树形dp问题。该类题目的特点是:给定一个树形结构,需要以每个节点为根进行一系列统计。 方法为两次扫描来求解: 第一次扫描时,任选一个点为根,在“有根树”上执行一次树形dp,在回溯时,...
1 2 3 4 5 ... 20
收藏数 36,097
精华内容 14,438
热门标签
关键字:

树形dp