[XXSY]树形DP专题 刷题笔记

· · 个人记录

树形DP专题

树的最大独立集

题目：

对于一棵有N个结点的无根树，选出尽量多的结点，使得任何两个结点均不相邻（称为最大独立集）。

题解：

用d[i][0]表示不选i ，以i为根的子树的最大独立集大小；d[i][1]表示选i ， 以i为根的子树的最大独立集大小

如果一个点没选，它的儿子选不选随便；如果一个点选了，它的儿子不能选

周年庆宴 Hdu 1520

题目：

很多领导，能形成一个树形关系网，这些领导参加一个party，每个人都有一个能使party活跃的值，但是每个人又不会跟自己的直接领导同时参加party。为使party气氛最好，求最好气氛值。

题解：

就是求树的最大独立集

二叉苹果树 URAL(GZ六中译)

题目：

有一棵苹果树，该苹果树是一棵二叉树，共N个节点，树节点编号为1~N，编号为1的节点为树根，边可理解为树的分枝，每个分枝都长着若干个苹果，现在要要求减去若干个分支，保留M个分支，要求这M个分支的苹果数量最多。

题解：

先明确不能去父留子。 设f[u][i]表示u的子树上保留i条边，至多保留的苹果数目。 其实就是树上01背包

选课

题目：

N 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b）。一个学生要从这些课程里选择 M 门课程学习，问他能获得的最大学分是多少？

题解：

树形背包

将每门课的直接先修课与其相连。易知，课与课间的先修关系构成一片森林。

建一个虚点0，把森林中每棵树的根节点与0号节点相连，这样森林就转成了以0号点为根的树。 DP时把0号节点列入必选的范围，选m+1门课即可

设dp[i][j]表示以i为根的子树中选择j个节点，获得的最大学分。

注意选择i的子树中的点的前提是i一定要被选。

LazyChild黑OJ

题目：

对于n种木马，有且仅有(n-1)对不能共存，并且对于每种木马，都存在至少一个木马与之不能共存。问最多可获取木马的个数。

题解：

树上最大独立集。

加分二叉树

题目：

设一棵 n 个节点的二叉树 tree 的中序遍历为(1,2,3,…,n)， 每个节点都有一个分数（均为正整数），tree 及它的每个子树都有一个加分。

任一棵子树 subtree（也包含 tree 本身）的加分 = subtree 的左子树的加分 × subtree 的右子树的加分 + subtree 的根的分数。

若某个子树为空，规定其加分为 1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。

试求一棵符合中序遍历为 (1,2,3,…,n) 且加分最高的二叉树 tree。要求输出

  1. tree 的最高加分。
  2. tree 的前序遍历。

题解：

一种常见的区间dp题，设f[i][j]表示节点i到节点j成树的最大加分。 按照区间长度从小到大的顺序进行区间dp即可。

具体地，二叉树的加分取决于谁是根，于是我们就在区间内枚举根k。

f[i][i]=a[i] f[i][j]=MAX(f[i][k-1]\times f[k+1][j]+f[k][k])(i\not=j)

因为要输出二叉树的前序遍历，所以再开一个root[i][j]表示 节点i到节点j组成的 加分最大的树 的根

战略游戏

题目：

求树的最小点覆盖数。（点覆盖：点集合使得任意一条边至少有一个端点在集合中）

题解：

用d[i][0]表示不选i ，以i为根的子树的最小点覆盖数；d[i][1]表示选i ， 以i为根的子树的最小点覆盖数

如果一个点选了，它的儿子选不选无所谓；如果一个点没选，它的所有儿子都要选

黑手党（Poj 3107 Godfather）

题目：

求树的重心。（树的重心满足：在删除它后，包含最多节点的剩余连通块的节点数最小）

题解：

板子。

通向自由的钥匙

题目：

通向自由的钥匙被放n个房间里，这n个房间由n-1条走廊连接。但是每个房间里都有特别的保护魔法，在它的作用下，我无法通过这个房间，也无法取得其中的钥匙。虽然我可以通过消耗能量来破坏房间里的魔法，但是我的能量是有限的。那么，如果我最先站在1号房间（1号房间的保护魔法依然是有效的，也就是，如果不耗费能量，我无法通过1号房间，也无法取得房间中的钥匙），如果我拥有的能量为P，我最多能取得多少钥匙？

题解：

题目可看作简单的树上背包，多叉树转二叉树后，设f(i,j)表示以i为根的二叉树分配j的能量所获得的最多钥匙数，在原多叉树上f(i,j)的意义即为 i的所有子孙、转树时在i后遍历到的兄弟、i自己 分配j的能量所获得的最多钥匙数。dp即可。

多叉树转二叉树的方法——左儿子右兄弟表示法： 在每个点存一个左节点，一个右节点，左节点表示与其同层的兄弟，右节点表示其儿子。

关于多叉树转二叉树

void Pre(int x)//多叉树转二叉树
{
    vis[x]=true;
    for(int i=1;i<=n;++i)
        if(!vis[i]&&graph[x][i])
        {
            r[i]=l[x];
            l[x]=i;
            Pre(i);
        }
    return;
}
void DFS(int x)//dp
{
    if(l[x])DFS(l[x]);
    if(r[x])DFS(r[x]);
    for(int i=0;i<=m;++i)
    {
        f[x][i]=f[r[x]][i];//注意这一句
        for(int j=0;j<=i-cost[x];++j)
             f[x][i]=max(f[x][i],key[x]+f[l[x]][j]+f[r[x]][i-j-cost[x]]);
    }
}

寻宝之旅

题目：

给一棵树，树上每个点有一定价值的宝藏。 探险队从其中的一点出发，每次他们可以留一个人在此点开釆宝藏，也可以不留，然后其余的人可以分成若干队向这一点相邻的点走去。 需要注意的是，如果他们把队伍分成两队或者两队以上，就必须留一个人在当前点，提供联络和通讯，当然这个人也可以一边开采此地的宝藏。 并且， 为了节约时间，队伍在前往开釆宝藏的过程中是不会走回头路的。 请计算探险队所能开釆的最大宝藏价值。

题解：

变形的树上背包

设f[i][j][0/1]表示以i为根的子树里有j个探险者,在i点留人/不留人，所能获取的最大宝藏价值

电脑网络 Hdu 2196

题目：

给定一棵树，对于每个点，求该点到与它距离最远的点的距离

题解：

换根dp

很经典的一道可以当板子背的题了

用f[x][0]表示 x的子树中 的点到x的最远距离，用f[x][1]表示 x的子树中 的点到x的次远距离，用f[x][2]表示 不在x的子树中 的点到x的最远距离

第一次dp求出f[x][0],f[x][1]，第二次dp用父亲的f[fa][0],f[fa][1]求出儿子的f[x][2]

最后答案即为 max(f[x][0],f[x][2])

偷天换日

题目：

艺术馆由若干个展览厅和若干条走廊组成。每一条走廊的尽头不是通向一个展览厅，就是分为两个走廊。每个展览厅内都有若干幅画，每幅画都有一个价值。经过走廊和偷画都是要耗费时间的。 警察会在n秒后到达进口，在不被逮捕的情况下你最多能得到的价值。

题解：

先把走廊和展览厅抽象成树模型：

每条走廊相当于树上的一个节点，过一个节点的时间代价为t_i。进口走廊为根节点。

走廊尽头通向展览厅，相当于该走廊代表的树上节点为叶子节点，且此处有x_i幅画。

走廊分叉为两条走廊，相当于该走廊代表的树上节点有两个儿子。

问题转成树上01背包。

坑点：

  1. 小偷在n-1秒时就必须离开
  2. 走廊必须走一来一回两遍

实现技巧：

因为建的是棵二叉树，所以采用“当前节点为u,左儿子为2u,右儿子为2u+1”的编点方式，线性存储二叉树，以优化空间、时间。

设dp[x][i]表示用i秒在第x个走廊及其子树偷画并返回走廊x，能偷的最多画数

dp[x][i]=max(dp[x][i],dp[x<<1][j]+dp[x<<1|1][i-j-t]);

（左儿子花j秒，右儿子花i-j-t秒，走走廊t秒）

电视网络（Poj 1155 TELE）

题目：

电视网络计划广播一个重要的足球比赛。他们的网络传输关系可以认为是一棵树。树的根即为广播比赛的电视台，叶子节点表示网络用户，其他节点表示中转站。

从一个节点向另一个节点传输广播的费用是给定的。总的传输费用为所有传输广播的边的费用之和。

每个用户愿意支付一定的报酬来观看足球比赛，电视网络决定是否给其提供广播信号。

写一个程序计算在电视网络不亏本的前提下（即看到比赛的用户的报酬之和-总的传输费用>=0），最多可以让多少人看到足球比赛。

题解：

直接用 “在不亏本的前提下最多可以让多少人看到比赛” 设状态的话，状态很难转移。

所以转换一下： 设dp[i][j]表示在以i为根的子树中，满足j个客户的需求所能获得的最大收益，那么在最终求最多客户时，只要求最大的dp[1][i]>=0的i就行了。

不难看出这是一个树上的分组背包。（背包的总容量相当于该点为根节点的子树中所有的用户数量；组数就是连接的儿子个数；把该节点的每个儿子看成一组，每组中的元素为选一个，选两个...选n个用户。)

dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[v][k]-$边$i-v$的花费$)

附1：多叉树上的背包详解

附2：分组背包：若干组物品，每组中的物品互相冲突（就是说每组中最多只能选一件物品），求最大价值

for(int k=1;k<=总共的组数;k++)//遍历所有的组k
    for(int j=v;j>=1;j--)//跟01背包类似，倒序枚举背包容量
        for(int i=1;i<=组中的元素个数;i++)//遍历这组中所有的元素

消防站（Poj 2152 Fire）

题目：

Z国有N个城市，编号为1~N。城市之间用高速公路连接，任意两个城市之间有且仅有一条路径。

最近，Z国火灾频发，于是政府决定在一些城市建立一些消防站，在城市K建立消防站需要花费W（K），每个城市的W可能不同。

如果不在城市K建立消防站，那么需要保证离K最近的消防站与K的距离不超过D（K）。每个城市的D可能不同。

为了节省开支，政府希望你计算满足要求的最小花费。

题解：

国家集训队2006论文集 陈启峰 (例题三就是)

河流 IOI(Amber译)

题目： 几乎整个Byteland王国都被森林和河流所覆盖。小点的河汇聚到一起，形成了稍大点的河。就这样，所有的河水都汇聚并流进了一条大河，最后这条大河流进了大海。这条大河的入海口处有一个村庄——名叫Bytetown.

在Byteland国，有n个伐木的村庄，这些村庄都座落在河边。目前在Bytetown，有一个巨大的伐木场，它处理着全国砍下的所有木料。木料被砍下后，顺着河流而被运到Bytetown的伐木场。Byteland的国王决定，为了减少运输木料的费用，再额外地建造k个伐木场。这k个伐木场将被建在其他村庄里。这些伐木场建造后，木料就不用都被送到Bytetown了，它们可以在运输过程中第一个碰到的新伐木场被处理。显然，如果伐木场座落的那个村子就不用再付运送木料的费用了。它们可以直接被本村的伐木场处理。

注：所有的河流都不会分叉，形成一棵树，根结点是bytetown。

国王的大臣计算出了每个村子每年要产多少木料，你的任务是决定在哪些村子建设伐木场能获得最小的运费。其中运费的计算方法为：每一吨木料每千米1分钱。

编一个程序：

1．从文件读入村子的个数，另外要建设的伐木场的数目，每年每个村子产的木料的块数以及河流的描述。

2．计算最小的运费并输出。

题解：

按照一般思路考虑，先设f[u][j]表示在u及u的子树建了j个伐木场的运费最小值。

但因为不知道各节点的木材具体运到多远，运费不好统计。

于是我们再加一个限制条件，设f[u][i][j]表示离u最近的建了伐木场的祖先为i，u及u的子树建了j个伐木场的运费最小值。

列状态转移方程，发现还要讨论在u建不建伐木场。

最后决定设四维的状态f[u][i][j][0/1]，u,i,j意义同上，0表示在u不建伐木场，1表示在u建伐木场

转移方程如下：

dp[x][anc][k][0] = Min(dp[x][anc][k][0],dp[v][anc][l][0] + dp[x][anc][k - l][0]);
dp[x][anc][k][1] = Min(dp[x][anc][k][1],dp[v][x][l][0] + dp[x][anc][k - l][1]);

ps.可以开一个动态栈记录祖先

又是DEBUG

题目：

Bugzilla由N个基地组成。这N个基地被N-1段双向地道连接在一起，每段地道都连接两个基地，并且保证任意两个基地之间都可以通过地道互相到达。Bug就藏在其中的某段地道中。

开始时rc可以乘坐运输机降落在任何一个基地。每次到达一个基地时，rc都可以选择呼叫运输机将他和他的部队运输到任意另一个基地，或者进入与这个基地相邻的一段地道进行搜索。但为了防止Bug跑进已经搜索过的地道，他在离开一个基地进入地道或登上运输机时一定会将这个基地炸毁。基地一旦被炸毁就不再和与它相邻的地道连接。但这样一来，如果进入的地道另一端的基地已经在之前被炸毁，rc和他的部下就将被永远困在地道中。因为地道生活并不有趣，所以在这种情况下rc是不会进入这段地道的。

不过，这也带来了一个问题，就是rc也许不能搜索所有的地道了。现在rc想知道的是他最多能搜索多少段地道。

题解：

题意转换：保留若干条链，让删去的边最少

贪心解决：

度=1：该点为链的一段，不用删

度=2：该点为链的中间，不用删

度>2：删去(度-2)条边，且优先删除和父节点连边

证明：设该点为u，u至少有2个儿子，设v1的子树为所有儿子的子树中最高的,v2的子树为次高的，那么保留树链“-v1-u-v2-”一定比保留树链“-fa-u-v1-”优

void DFS(int x,int fa)
{
    vis[x]=1; 
    for(int i=head[x];i;i=nxt[i])
        if(!vis[e[i]]) DFS(e[i],x);
    if(du[x]>2)n-=du[x]-2,du[fa]--;//删去连父亲的边,父亲度数-1 
    return;
}

kingdom

CF613D Kingdom and its Cities

题目：

一个王国有n座城市，城市之间由n-1条道路相连，形成一个树结构，国王决定将一些城市设为重要城市。

这个国家有的时候会遭受外敌入侵，重要城市由于加强了防护，一定不会被占领。而非重要城市一旦被占领，这座城市就不能通行。

国王定了若干选择重要城市的计划，他想知道，对于每个计划，外敌至少要占领多少个非重要城市，才会导致重要城市之间两两不连通。如果外敌无论如何都不可能导致这种局面，输出-1

题解：

先建出虚树，不难发现要删最少的点肯定是挑虚树上的点删。

考虑如何求解题目的问题:

设g[x]表示以x为根的子树中有没有关键点与x联通(如果x为关键点则g[x]为true），

设$v$为$x$的儿子节点，首先$f[x]$=$∑f[v]$，然后判断$x$： ①如果$x$为关键点，那么$f[x]+=∑g[v]$，也就是说，将它和每个没断的关键点子孙全部断掉； ②如果$x$不是关键点，那么分三种情况：如果它有多个关键点子孙都没断，那就把它自己切掉即可，$f[x]++$；否则，如果就一个关键点没断就留到它的祖宗那去（也许到时候能和别的一起断掉），$g[x]=true$；如果一个都没，$g[x]=false$。 ### happy 题目： 给出一个n个节点的树，两点之间有且仅有一条路径相连。 给出m个点对xi,yi，如果添加一条双向边边{u,v}后xi和yi在一个简单环中，则称这条边是happy的，happy值为这个简单环的点数。 请你求出对于点对xi,yi，所有happy的边的happy值的平均数。 **注意，简单环是包括自环的。** 题解： 先看什么样的边是happy的：对于点对$x,y$（$dep[x]<dep[y]$）, 若$lca(x,y)==x$:一端点在$x$的子树外，一端点在$y$的子树内的边是happy的 若$lcs(x,y)\not=x$:一端点在$x$的子树内，一端点在$y$的子树内的边是happy的 （注意讨论happy边的端点在$x,y$的特殊情况） 手推一下 点对$x,y$的 happy边的happy值总和 、happy边总数 的式子，可以把式子整理成两部分，一部分只与$x$有关，一部分只与$y$有关。 正着做一次树形dp，反着做一次树形dp即可预处理出来。 ### chocolate [CF633F The Chocolate Spree](https://www.luogu.com.cn/problem/CF633F) 题目： 大M的巧克力树由n个节点组成，每个节点i上都有v[i]个巧克力，巧克力树上有n-1条树枝连接这整棵树（保证任意两点间存在一条路径）。 Alice和Bob一开始都可以选择一个出发起点并获得该节点上的所有巧克力，Alice先选。 接下来，Alice和Bob会依次移动到自己节点相邻的节点上，并获得该节点上的所有巧克力。但是，任意节点都只能被经过一次，若Alice走过某个节点x，则Bob不能到达这个节点，当然Alice也不能走回x。 请问他们总共最多能获得多少巧克力？ 题解： 题意转换：求树上两条不相交链的最大点权和 最自然的想法：设$dp[i][j]$表示在$i$的子树中选$j$条不相交链的最大点权和。 但转移时发现还要考虑选的链有没有延伸到子树根节点，因为只有延伸到子树根节点的链才能在根节点的祖先方向加长。 最终决定设$dp[i][j][0/1]$表示在以$i$为根的子树中选$j$条不相交链，有/没有链延伸到子树根节点，能选到的最大点权和。 ![](https://cdn.luogu.com.cn/upload/image_hosting/bnm0mnlr.png) ### Born Slippy [HDU 5735 Born Slippy](http://acm.hdu.edu.cn/showproblem.php?pid=5735) 题目： 给定一棵有根树，节点标号从1到n，同时规定1为根。每个节点有一个权值 wi 。 对于任意的 s∈{1,2,...,n} ，我们想找到一个序列（序列中的元素是节点） v1,v2,...,vm 使得： 1. v1=s 且 vi 是 vi−1 的祖先 (1<i≤m) 2. $f(s)=w_{v_1}+\sum_{i=2}^mw_{v_i}\space opt\space w_{v_{i-1}}$的值最大。 操作x opt y表示两个数之间的AND, OR, XOR位运算操作。 题解： ![](https://cdn.luogu.com.cn/upload/image_hosting/7ui1e2b8.png) 总结：看到题首先想到枚举祖先的$O(n^2)$算法，但一定过不了。 观察一下题目，发现w的值不超过$2^{16}$，想到维护$ds(x)$表示满足$w[j]=x$的最大的$dp[j]$,在更新$dp[i]$时枚举$w[j]$。但$2^{16}$也很大，没有太大的优化，顺着这个思路下去，就有了题解中**折半枚举**的神奇方法。 ### “杀人”游戏 题目： 游戏中有N个人，这里的人分为两类：恶魔、平民。 现在这N个人，每个人都要指控另一个人。一个恶魔一定是指控一个平民，而一个平民指控的人可能是恶魔也可能是平民。现在给出这N个人指控的关系，问满足这种指控关系的前提下，最多可以有多少个恶魔？ 题解： 问题相当于求**最大独立集**。 因为每个点都有且仅有一条出边，所以建出的图一定是一颗**基环外向树**。 可以用**二次dp法**（将一条边强行断开处理一遍，然后强行连上再处理一遍）解决。 ### thr [[POI2014]HOT-Hotels 加强版](https://www.luogu.com.cn/problem/P5904) 题目： 给出一棵 n 个点的无根树，请在这棵树上选三个互不相同的节点，使得这个三个节点两两之间距离相等，输出方案数。 题解： [题解1](https://www.luogu.com.cn/blog/83547/solution-p5904) [题解2](https://www.luogu.com.cn/blog/128870/p5904-post) ### 重建道路 [重建道路](https://www.luogu.com.cn/problem/P1272) 题目： 有一颗N个点的树。有一些边，一旦被删，就会使一棵含有P个节点的子树和整颗树的其它部分分离。求这些边的最小数目。 题解： 用$f(i,j)$来表示第$i$个点为根的子树，保留$j$个点（包括自己）删去边的最小值，我们用$a[i]$来记录出度，也就是几个儿子，因此： 初始化： $f(i,1)=a[i]

方程：

f(now,j)=max(f(now,j),f(now,j-k)+f(v,k)-1)

(-1是因为v和now节点之间相连的那一条边不删)

注意：

  1. 我们要获得的子树的根并不一定要是整棵树的根节点，因此我们需要枚举每一个节点为根的小子树，看看哪一个删边数是最小的
  2. 小子树的根i不是整棵树的根节点时，正确删边数是f[i][p]+1，因为要删去i与i的父亲相连的边

hdu1011

题目：

有n个洞组成一棵树，你有m个士兵，你从1号房间开始攻打，每个洞有a个"bugs"和b的价值。你的一个士兵可以打20个"bugs"，为了拿到这个洞的价值b你必须留下k个士兵消灭这个洞的所有"bugs"（k*20>="bugs"的数量，且留下的士兵不可以再去攻打其他的洞，且必须攻打了前面的洞才可以攻打后面的洞）。问你花费这m个士兵可以得到的最大价值是多少。

题解：

树上背包

hdu1561

题目：

ACboy很喜欢玩一种战略游戏，在一个地图上，有N座城堡，每座城堡都有一定的宝物，在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因，有些城堡不能直接攻克，要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮ACboy算出要获得尽量多的宝物应该攻克哪M个城堡吗？

题解：

题目给的城堡形成一个森林，添加一个超级根把森林连在一起就是树了

然后跑树上背包即可

HDU2196

题目：

给你一棵树，已知每条边的权值。求每个点所能达到的最远点的距离。

题解：

经典题，前面有很像的。

hdu2546

题目：

电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。 某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。

题解：

贪心+动态规划（背包）：

先从总钱数扣除5元，用来买最贵的菜，然后用剩余的钱来背包。

hdu5326

题目：

现在有一个有n个人的公司，然后每个人除了boss外都有一个直接领导者，然后如果是直接或间接领导的话，那么都可以说是A管理了B。然后问你有多少个人管理着k个人。

题解：

树形dp求一下siz[u]表示以u为根的子树的节点数。