首页 > 其他分享 >树形 dp

树形 dp

时间：2024-08-19 11:48:45浏览次数：11  
标签：int max son 树形 为根 节点 dp

在树上运行的 dp 叫做树形 dp。

题单。

树形 dp 入门问题

例 1.1：没有上司的舞会

我们发现，对于一个节点，要么选或不选，且题目中要求求出权值最大的方案，不妨分别设 \(dp_{i,0},dp_{i,1}\) 为在以 \(i\) 为根的子树中，第 \(i\) 个点选或不选情况下的最大权值。
那么可以得到

\[dp_{i,0}=\sum\max(dp_{son,0},dp_{son,1}) \]

\[dp_{i,1}=\sum dp_{son,0} \]

因为我们在转移 \(i\) 的时候要先计算好 \(son\) 的 dp 值。可以用 DFS 来实现。

\(\text{Code:}\)

void dfs(int x){
	dp[x][1]=w[x];
	for(int i=ver[x];i;i=nxt[i]){
		dfs(to[i]);
		dp[x][1]+=dp[to[i]][0];
		dp[x][0]+=max(dp[to[i]][0],dp[to[i]][1]);
	}
	return;
}

该算法时间复杂度 \(O(n)\)。

树形 dp 经典模型

树上背包

例 2.1：[CTSC1997] 选课

由于是最值，以及存在「费用」和「价值」两个方面，很自然联想到背包问题，设 \(dp_{u,k}\) 为以 \(u\) 为根的子树中，选取 \(k\) 门课的最大学分。由于节点 \(u\) 本身要选，我们将剩下的 \(k-1\) 门课分给 \(u\) 的各个子节点。使得

\[dp_{u,k}=s_u+\max\sum dp_{son_i,t_i}(\sum t_i=k-1) \]

但这个方程不好转移，直接枚举会达到指数阶，我们仿照线性 dp。在状态中添上一维：另 \(dp_{u,i,k}\) 表示以 \(u\) 为根的子树中，前 \(i\) 颗子树，选取 \(k\) 门课的最大学分。这样，\(dp_{u,i,k_1}\) 只和 \(dp_{u,i-1,k_2}\) 有关。这里面也体现出了问题的最优子结构

\[dp_{u,i,k}=s_u+\max(dp_{u,i,k},dp_{u,i-1,k-t}+dp_{son,all,t}) \]

其中 \(son\) 表示 \(u\) 的儿子，\(all\) 表示 \(son\) 的子节点个数。我们只需要枚举 \(k\) 和 \(t\)。注意到节点 \(u\) 转移时，\(dp_{u,i,k_1}\) 只和 \(dp_{u,i-1,k_2}\) 有关，而 \(dp_{son,all,t}\) 只用保留最终状态，可以用滚动数组优化掉一维

\[dp_{u,k}=s_u+\max(dp_{u,k},dp_{u,k-t}+dp_{son,t}) \]

空间复杂度显而易见 \(V(nm)\)，因为没对点只会枚举一次，所以时间复杂度 \(O(nm)\)。

\(\text{Code:}\)

int sum=0;dp[u][0]=0;
for(int i=ver[u];i;i=nxt[i]){
    int v=to[i],son;
    if(v==fa)continue;
    son=dfs(v,u);
    sum+=son;
    for(int j=sum;j>0;j--){
        for(int k=1;k<=min(j,son);k++){
            dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]-val[i]);
        }
    }
}
//这并非P2014正确代码，仅做树形背包的模型参考

换根 dp

例 2.2：[POI2008] STA-Station

我们发现，对于一棵无根树，以任意一个节点为根，树上所有节点的深度和有可能不一样的。所以一个朴素的办法是枚举任意一个根节点，遍历整棵树。时间复杂度 \(O(n^2)\)，无法通过 \(10^5\) 的数据

我们可以利用已经求过的信息来优化这个过程。我们另 \(d_x\) 表示以 \(1\) 为根时，以 \(x\) 为根的子树的深度和。\(f_x\) 表示以 \(x\) 为树根时的深度和，\(siz_x\) 表示以 \(1\) 为根时，以 \(x\) 为根的子树大小。显然，\(f_1=d_1\)。

假设 \(u\) 是 \(v\) 的父亲，且 \(f_u,d_u,d_v\) 求解完成，我们如何快速求出 \(f_v\)？不难发现，\(f_v\) 的构成有两部分。

  • 以 \(1\) 为根时，\(v\) 的子树的深度和（就是 \(d_v\)）
  • 其他，也就是说 \(u\) 除了儿子 \(v\) 以外的部分的深度和。

当以 \(u\) 为根时，部分二的大小就是 \(f_u-d_v-siz_v\)，这一部分的节点个数是 \(n-siz_v\)（\(u\) 不一定是 \(1\)）。当根从 \(u\) 换到 \(v\) 时，部分二的深度会整体加一，因为他们多了一个共同的祖宗———\(v\) 节点。如果可以理解 Treap 中旋转的概念，可以更好的理解这一点。

综上可得：\(f_v=d_v+(f_u-d_v-siz_v)+(n-siz_v)=f_u+n-2\times siz_v\)

本题中的 \(d_x\) 没有用处。我们只需要在进行两次 DFS。第一次求出 \(siz_x\)。第二次求出 \(f_x\)。

例 2.3：[USACO12FEB] Nearby Cows G

以下均将原树成为以 \(1\) 为根节点的树。

\(d_{x,k}\) 表示在原树中，以 \(x\) 为根的子树里距离 \(x\) 不超过 \(k\) 的点的点权和，\(f_{x,k}\) 表示以 \(x\) 为根是距离 \(x\) 不超过 \(k\) 的点的点权和。

显然 \(f_{1,k}=d_{1,k}\)，\(f_{x,1}=d_{x,k}+w_{fa}\)。对于 \(f_{x,k}\) 分为两部分

  • 原树中 \(x\) 子树中的部分，即 \(d_{x,k}\)

  • 其他部分，也就是距离其父节点距离不超过 \(k-1\)，且不包括 \(x\) 子树的部分。

转移方程

\[f_{x,k}=f_{fa,k-1}-d_{x,k-2}+d_{x,k}(k\ge2) \]

\(\text{Code:}\)

void dfs1(int x,int fa){
    for(int i=0;i<=k;i++)d[x][i]=w[x];
    for(int i=ver[x];i;i=nxt[i]){
        if(to[i]==fa)continue;
        dfs1(to[i],x);
        for(int j=1;j<=k;j++)d[x][j]+=d[to[i]][j-1];
    }
    return;
}
void dfs2(int x,int fa){
    for(int i=ver[x];i;i=nxt[i]){
        if(to[i]==fa)continue;
        f[to[i]][1]=d[to[i]][1]+w[x];
        for(int j=2;j<=k;j++)f[to[i]][j]=d[to[i]][j]+f[x][j-1]-d[to[i]][j-2];
        dfs2(to[i],x);
    }
    return;
}

时间复杂度 \(O(nk)\)。

小结

可以看出来，这种方法一般会进行两次 DFS。每次的时间复杂度 \(O(n)\)。

基环树 dp

定义

基环树：\(n\) 个点 \(n\) 条边组成的连通图

基环树森林：\(n\) 个点 \(n\) 条边，但不一定联通

解题思路：找环，转换为树形 dp 或环形 dp。

找环方法

  • 并查集

在读入边的时候动态维护连通块，如果此时加入一条边 \((u,v)\)。两点已位于同一连通块时，那么这个联通块内的点构成一个环

该方法代码量少，适合在连通图基环树上找环，同时也可以维护一些信息

  • DFS

开一个 \(vis\) 数组标记，DFS 即可。代码长，但空间小。

例题 2.4：城市环路

基环树中的边最小支配集问题。我们可以任意去掉基环树上环的任意一条边 \((u,v)\)，然后分别以 \(u,v\) 为根节点，进行一次树形 dp。

问题在于，这里其实还有一条边 \((u,v)\)。\(u,v\) 不可以同时选。基于这个特性，我们会发现要么 \(u\) 不选，要么 \(v\) 不选。每次树形 dp 完后直接拿 $dp_{u,0},dp_{v,0} $ 来更新答案。树形 dp 直接仿照「没有上司的舞会」哪一题即可。

scanf("%lld\n",&n);
for(int i=0;i<n;i++)scanf("%lld",w+i),f[i]=i;
for(int i=1,u,v;i<=n;i++){
    scanf("%d %d",&u,&v);
    if(found(u)!=found(v))f[found(u)]=found(v),add(u,v),add(v,u);
    else a=u,b=v;
}
scanf("%lf",&k);
dfs(a,-1),ans=dp[a][0];
dfs(b,-1),ans=max(ans,dp[b][0]);
printf("%.1lf\n",ans*1.0*k);

树形 dp 拓展问题

主要是一些有意思的题目

例 3.1：[SDOI2006] 保安站岗

同样是一道最小支配集问题，和「没有上司的舞会」相像，只不过这次要求相邻两点必须选一个。

举个例子，加入树中有一条链 1-2-3-4。如果选择 \(1,4\) 在本题是合法的，但在「没有上司的舞会」这题是不可行的。

我们需要进一步考虑：

  • \(dp_{i,0}\)：以 \(i\) 为根的子树中，选择点 \(i\) 的最小权值和。

如果点 \(i\) 选择，那么他的儿子无论选不选都可行：

\[dp_{i,0}=\sum \min\{dp_{i,0},dp_{i,1},dp_{i,2}\} \]

  • \(dp_{i,1}\)：以 \(i\) 为根的子树中，不选择点 \(i\)，点 \(i\) 的父亲被选择的情况下子树的最小权值和。

因为点 \(i\) 没有选择，所以 \(i\) 的儿子不能通过 \(i\) 选择来转移：

\[dp_{i,1}=\sum\min\{dp_{i,0},dp_{i,2}\} \]

  • \(dp_{i,2}\)：以 \(i\) 为根的子树中，不选择点 \(i\)，点 \(i\) 的儿子被选择的情况下子树的最小权值和。

因为点 \(i\) 没有选择，所以 \(i\) 的儿子不能通过 \(i\) 选择来转移。因此和上一种情况相同，但必须同时保障必须有一个儿子选择 \(dp_{son,0}\)。

void dfs(int x,int fa){
    dp[x][0]=w[x];int f=0,flag=0,minn=1e9;
    for(int i=ver[x];i;i=nxt[i]){
        if(to[i]==fa)continue;
        dfs(to[i],x);
        dp[x][0]+=min(min(dp[to[i]][0],dp[to[i]][1]),dp[to[i]][2]);//自己控制
        dp[x][1]+=min(dp[to[i]][0],dp[to[i]][2]);//父亲控制
        if(dp[to[i]][0]<dp[to[i]][2])dp[x][2]+=dp[to[i]][0],flag=1;//儿子控制
        else dp[x][2]+=dp[to[i]][2];
        f=1,minn=min(minn,dp[to[i]][0]-dp[to[i]][2]);
    }
    if(!f)dp[x][2]=1e9;
    if(x==1)dp[x][1]=1e9;
    if(f&&!flag)dp[x][2]+=minn;
    return;
}

最小支配集\(\text{ Plus}\)。也存在贪心做法

例 3.2：[ZJOI2006] 三色二叉树

树上染色，经典问题，下文以绿色节点的最大数为例。

设 \(dp_{x,0/1/2}\) 分别表示节点 \(x\) 染上绿，红，蓝三种颜色的情况下，子树内绿色节点数量的最大值，分三种情况

  • \(x\) 没有儿子

\(dp_{x,0}=1,dp_{x,1}=0,dp_{x,2}=0\)

  • \(x\) 有一个儿子

如果 \(x\) 染成绿色，那么儿子就不能染绿色，取较大值，加上本身染成绿色的 \(1\)。

\[dp_{x,0}=\max(dp_{son,1},dp_{son,2})+1 \]

反之如果不然绿色，染成颜色 \(i\)。

\[dp_{x,i}=\max(dp_{son,col1},dp_{son,col2})(col1\ne col2\ne i) \]

  • 如果有两个儿子

由于三个儿子都不一样。情况就很简单了，可以开一个数组来代表情况。

void dfs(int x){
    dp[x][0][1]=dp[x][1][1]=dp[x][2][1]=1e6;
    if(!ls[x]){
        for(int i=0;i<=2;i++)dp[x][i][0]=dp[x][i][1]=0;
        dp[x][0][0]=1,dp[x][0][1]=1;
    }else if(!rs[x]){
        dfs(ls[x]);
        for(int i=1;i<=2;i++)dp[x][0][0]=max(dp[x][0][0],dp[ls[x]][i][0]+1),dp[x][0][1]=min(dp[x][0][1],dp[ls[x]][i][1]+1);
        for(int i=1;i<=2;i++){
            for(int j=0;j<=2;j++){
                if(i==j)continue;
                dp[x][i][0]=max(dp[x][i][0],dp[ls[x]][j][0]),dp[x][i][1]=min(dp[x][i][1],dp[ls[x]][j][1]);
            }
        }
    }else{
        dfs(ls[x]),dfs(rs[x]);
        for(int i=0;i<=2;i++){
            int a=other[i][0],b=other[i][1];
            dp[x][i][0]=max(dp[x][i][0],max(dp[ls[x]][a][0]+dp[rs[x]][b][0],dp[ls[x]][b][0]+dp[rs[x]][a][0])+(i==0?1:0));
            dp[x][i][1]=min(dp[x][i][1],min(dp[ls[x]][a][1]+dp[rs[x]][b][1],dp[ls[x]][b][1]+dp[rs[x]][a][1])+(i==0?1:0));
        }
    }
}

这种树上染色的状态很好设计，但对于状态的转移则考验分类讨论能力。

例 3.3：[ZJOI2007] 时态同步

我们另 \(dp_x\) 表示将以 \(x\) 为根的子树全部时态同步的代价，\(d_x\) 则表示从 \(x\) 节点被激励到其子树全部时态同步的时间。

我们发现，每次操作只能将传导速度后延，而不能加速。也就是说 \(d_x\) 的取值与最大的儿子相关。即
\(d_x=\max d_{son}+val_{x,i}\)。特殊的，一个节点如果没有儿子，则 \(d_x=0\)。

而 \(x\) 为根的子树中的所有节点都必须延后到这个时态，我们就可以很轻松的写出转移方程。

void dfs(int x,int fa){
    dp[x]=0;ll maxn=-1;
    for(int i=ver[x];i;i=nxt[i]){
        if(to[i]==fa)continue;
        dfs(to[i],x);
        maxn=max(maxn,d[to[i]]+val[i]);
    }
    for(int i=ver[x];i;i=nxt[i]){
        if(to[i]==fa)continue;
        dp[x]+=dp[to[i]]+maxn-d[to[i]]-val[i];
    }
    d[x]=(maxn==-1?0:maxn);
    return;
}

例 3.4：[HNOI/AHOI2018] 道路

注意到给出的树是一棵满二叉树，且 \(a_i,b_i\) 都很小，可以从这里下手，设计状态。

\(dp_{x,i,j}\) 表示 \(x\) 节点到根节点的路上有 \(i\) 条为翻修的公路和 \(j\) 条未翻新的铁路。应为「每个城市翻修恰好一条通向它的道路」。所以要么修铁路，要么修公路，可得

\[dp_{x,i,j}=\max(dp_{ls,i,j}+dp_{rs,i,j+1},dp_{ls,i+1,j}+dp_{rs,i,j}) \]

特殊的，如果这个节点是村庄，那么

\[dp_{x,i,j}=c_x\cdot(a_x+i)\cdot(b_x+j) \]

最后的结果就是 \(dp_{1,0,0}\)。这题的转移和方案设计尤为重要。

void dfs(ll x,ll l,ll r){
    if(x>=n){
        for(int i=0;i<=l;i++)
            for(int j=0;j<=r;j++)
                dp[x][i][j]=c[x]*(a[x]+i)*(b[x]+j);
    }else{
        dfs(ls[x],l+1,r),dfs(rs[x],l,r+1);
        for(int i=0;i<=l;i++)
            for(int j=0;j<=r;j++)
                dp[x][i][j]=min(dp[ls[x]][i][j]+dp[rs[x]][i][j+1],dp[ls[x]][i+1][j]+dp[rs[x]][i][j]);
    }
    return;
}

例 3.5：[HAOI2009] 毛毛虫

我们写这道题之前，要理解毛毛虫本质。

  1. 从树中抽出一条链

  2. 抽出与链上节点相连的所有点

毛毛虫只有两种情况，一是单独存在于某个节点的子树中，而是经过这个节点，我们可以把它看成带权的树的直径，树形 dp 求解就行

void dfs(int x,int fa){
    int cnt=0;
    for(int i=ver[x];i;i=nxt[i],cnt++){
        if(to[i]!=fa)dfs(to[i],x);
    }
    d[x]=max(1,cnt);
    for(int i=ver[x];i;i=nxt[i]){
        if(to[i]==fa)continue;
        ans=max(ans,d[x]+d[to[i]]);
        d[x]=max(d[to[i]]+cnt-1,d[x]);
    }
}
//这种写法要特判n=1的情况

标签：int,max,son,树形,为根,节点,dp
From： https://www.cnblogs.com/zuoqingyuan/p/18367026

相关文章

  • 状压 dp
    定义在动态规划中，可能存在以“集合”为状态的动态规划，应为集合不易表示，所以通常用一个二进制数来表示集合。具体的，二进制数的第\(i\)位即表示当前集合是否包含第\(i\)个元素。技巧因为许多位运算的运算优先级很迷，所以搞不明白就尽量用括号。二进制操作将\(n\)位二进......
  • @Async使用ThreadPoolTaskExecutor 多线程
    SpringBoot中的线程池ThreadPoolTaskExecutor，@Async的使用线程池@Configuration@EnableAsyncpublicclassExcutorConfig{@Bean(name="ThreadPoolTaskExecutor")publicThreadPoolTaskExecutorThreadPoolTaskExecutor(){ThreadPoolTaskExecutorex......
  • UDP的可靠性传输——KCP
    目录一：TCP是怎么做到可靠的？1、UDP和TCP的区别 2、ARQ协议(AutomaticRepeat-reQuest)2.1、ARQ协议-停等式(stop-and-wait)2.2、ARQ协议-回退n帧(go-back-n)2.3、ARQ协议-选择性重传(selectiverepeat)3、RTT和RTO4、流量控制5、如何进行流量控制（滑动窗口）6、流量控......
  • 【TCP/IP】UDP协议数据格式和报文格式
    学习一个网络协议，主要就是学习“数据格式”/“报文格式”源端口/目的端口端口号是属于传输层的概念UDP报头使用两个自己的长度来表示端口号之所以端口号的范围是0~65535，是因为底层网络协议做出了强制要求如果使用一个10w这样的端口，就会在系统底层被“截断”UDP......
  • ThreadPoolExecutor详解
    恰逢经济下行，鄙人工作、生活日趋艰难，原本美好的愿望，如今只能成为奢望。不知如何是好的我，只能精研近几年来因浮躁而荒废的知识。今天就想跟大家聊一个对我来讲看似熟悉实则陌生的工具——ThreadPoolExecutor。熟悉是因为在我负责的项目中它是一个出镜率最高演员；陌生是因为我对其......
  • 序列（dp+矩阵加速）
    第2题   序列 查看测评数据信息给定一个数集A，现在你需要构造一个长度为k的序列B，序列B的元素从数集A中任意挑选，要求B中任意相邻的两个数字的异或值二进制表示中1的个数是3的倍数，请问B的有多少种合法的构造方案？两种方案不同当且仅当存在B[i]在A中的位置不同。输入格式......
  • (nice!!!)LeetCode 552. 学生出勤记录 II（动态规划dp递归版、记忆化dfs）
    题目：552.学生出勤记录II思路：记忆化搜索dfs，细节看注释classSolution{public:constintmod=1e9+7;//状态f[u][a][b]表示：在选择第u个位置前，缺勤次数为a次，且当前连续迟到次数为b次时，可以得到的合法出勤次数intf[100010][5][5];intdfs(intu,int......
  • 幸运数（dp+矩阵加速）
    第1题   幸运数 查看测评数据信息小明认为只有数字4和7是幸运数字，其他数字都不是。如果一个整数的每个数字都是幸运数字，那么该整数就是幸运整数。给出一个数组numbers[1...n]。一个长度为L的幸运数列A[0],A[1],A[2],...A[L-1]必须同时满足：1、对于0<=i<L,    A[......
  • DP学习笔记
    动态规划算法与分治法类似，是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始......
  • 【动态规划、dp】[CSP-J 2022] 上升点列 题解
    题目描述在一个二维平面内，给定nnn个整数点(xi......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99