机械网站开发方案,系列推广软文范例,如何搭建高品质网站,佛山手工外发加工网基本概念#xff1a;
换根dp是树上dp的一种
我们在什么时候需要用到换根dp呢#xff1f;
当题目询问的属性#xff0c;是需要当前结点为根时的属性#xff0c;这个时候#xff0c;我们就要使用换根dp
换根dp的基本思路#xff1a;
假设题目询问的的属性为x
通常我们…基本概念
换根dp是树上dp的一种
我们在什么时候需要用到换根dp呢
当题目询问的属性是需要当前结点为根时的属性这个时候我们就要使用换根dp
换根dp的基本思路
假设题目询问的的属性为x
通常我们会进行两次dfs
第一次dfs我们选取任意一个结点作为给出的无根树的根,对其进行dfs并求出这个根的x以及一些其他辅助数组即节点与其子树的一些属性关系
第二次dfs我们记dp[i]为对于结点i而言节点i作为树的根时我们要求的属性x
那么令当前结点为u其子节点为v我们需要对推到出dp[u]转移到dp[v]的转移方程从而成功求出结点v作为根时的属性x如此递归下去直到将所有结点的dp值都求出来我们就可以求得题目的询问答案了
例题1
题目链接P3478 [POI2008] STA-Station - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目大意
给出一棵有n个节点的树求出这样的一个节点使得以这个节点为根时所有节点的深度之和最大
题目分析由于题目很直白地讲了是要求以节点为根时的属性那么当然是采用换根dp的方法
由于是深度之间的转移我们设数组s[i]表示的是以节点i为根的子树的深度之和
我们先选取1号节点为根进行第一次dfs预处理出s数组的值以及dp[1]的值
之后我们需要用第二次dfs进行关系转移
我们考察当前节点u以及其子结点v
当根从u转移到v时以v为根的子树的每个结点的深度都减小了1也就是总深度减小了s[v]
而对于以u为根的且排除了v结点的子树而言他们每个结点的深度都增大了1也就是总深度增大了n-s[v]
由此我们可以推到出当根由u转到v时总深度从dp[u]变到dp[v]的变化是增加了n-2*s[v]
即得转移方程:dp[v]dp[u]n-2*s[v]
至此我们只需要用第二次dfs求出每个节点的dp值最后再从1到n遍历出最大的dp值其对应的节点编号即为询问答案
实现代码
#include cstdio
#include iostream
using namespace std;
// 换根dp
// 用s[i]表示以i为根时其子树的结点个数
// 令u为当前结点
// v为当前结点的子结点
// 则有s[u]s[v]1
// 第一次dfs选取任意一个根来预处理出所有的s[i]//换根的状态转移
//dp[i]表示以i为根时所有结点的深度之和
//令当前根为uv为其子结点
//则将根由u转到v时
//所有在v的子树上的结点深度都会减少1那么总深度就减少了s[v]
//所有不在v的子树上的结点的深度都会增加1那么总深度就增加了n-s[v]
//由此我们得知dp[v]dp[u]n-2*s[v]此为状态转移方程
//我们第二次dfs来进行这个操作//最后只需遍历dp[i]找到最大的即可
const int N1E610,MN1;
int n;
//链式前向星加边
int to[M],nxt[M],h[N],tot;
void add(int a,int b){to[tot]b;nxt[tot]h[a];h[a]tot;
}
unsigned long long s[N],dp[N],dep[N];
void dfs1(int f,int u){dep[u]dep[f]1;s[u];for(int ih[u],v;vto[i];inxt[i]){if(vf) continue;dfs1(u,v);s[u]s[v];}
}
void dfs2(int f,int u){for(int ih[u],v;vto[i];inxt[i]){if(vf) continue;dp[v]dp[u]n-2*s[v];dfs2(u,v);}
}
int main(){cinn;for(int i1,a,b;in;i){cinab;add(a,b);add(b,a);}dep[0]-1;dfs1(0,1);for(int i1;in;i) dp[1]dep[i];dfs2(0,1);unsigned long long max0;int ans;for(int i1;in;i)if(dp[i]max){maxdp[i];ansi;}coutans;return 0;
}
例题2
题目链接3585 -- 积累度 --- 3585 -- Accumulation Degree (poj.org)
题目大意定义A[i]表示的是结点i所能流到所有叶子结点的最大流量之和。其中由一个结点流向另一个节点的流量不能大于连接这两个结点的边的权值。
题目分析
由于流量是由父结点流向子结点这使得dfs不好处理不知道一开始要流多少有可能等于边权也有可能小于边权
所以我们选择把流量从子结点向父结点转移也就是说我们认为一个子结点v需要的流量为x那么回去找它的父结点u如果连接u与v的边权w大于等于x那么父结点u所需要的流量就增加x否则父结点所需要的流量只能增加w因为它最多只能流w到子结点v上
由此我们设出数组s1[i]表示的是i结点所需要的流量大小由上述可以写出s1数组的转移方程令当前结点为u其子结点为v那么s1[u]s1[v]w?w:s1[v]
又由于叶子结点v没有子结点了那么它所需要的流量就应该初始化为连结到v的边的权值因为它最多就只能要那么多。
怎么找到叶子结点呢只要注意到其入度为1就好了
这样我们就可以选取一个结点作为根进行第一次dfs预处理出s1数组
这里注意不能选取叶子结点作为第一次dfs的根因为会丢失掉其s1的值
第二次dfs:
设dp[u]其意义就是A[u]那么我们就需要推导其转移方程
考察当前根结点u转移到其子节点v
dp[u]表示u结点所需要的流量那么这部分流量可以被分为两部分
一部分是v结点所转移到u的流量我们记为Q1
另一部分是除了v节点外其他子节点所需要的流量我们记为Q2则有Q2dp[u]-Q1 考察v结点转移到u的流量
当v结点所需的流量s1[v]w时w为边权v只能转移w给u此时Q1w
而当s1[v]w时v能转移s1[v]给u此时Q1s1[v] 当根由u转到v时Q2这部分流量就需要转到v上由于边权w的限制Q2的转移量可能会发生变化我们设其转移量为Q2
当Q2w时只能转移w给v此时Q2w
而当Q2w时就转移Q2给v此时Q2dp[u]-Q1
而对于节点v而言当其成为根后其所需的流量一部分来自于Q2的转移另一部分来自于结点v自身所需的流量s1[v]也就是说dp[v]Q2s1[v]
至此我们成功推导出了状态转移方程只需进行第二次dfs即可求出所有的dp值进而求出最大值
细节问题当v为叶子结点时由于其所需的s1[v]来自于一开始的初始化当它成为根后其实并不需要s1[v]这一部分的贡献因此我们要将这个值减去
实现代码
#include iostream
#include cstdio
using namespace std;
const int N 2E5 10, M N 1;
int to[M], nxt[M], w[M], h[N], tot;//链式前向星
int in[N];//记录入度
int n, T;
//加边
void add(int a, int b, int c) {to[tot] b;w[tot] c;nxt[tot] h[a];h[a] tot;in[b];
}long long s1[N], dp[N];
//第一次dfs获取s1数组
void dfs1(int f, int u) {for (int i h[u], v; v to[i]; i nxt[i]) {if (f v) continue;//当v为叶子结点时dfs其之前先初始化s1[v]的值为边权if (in[v] 1) s1[v] w[i];dfs1(u, v);//dfs完后子结点向父结点转移s1的值s1[u] s1[v] w[i] ? s1[v] : w[i];}
}
//第二次dfs
void dfs2(int f, int u) {for (int i h[u], v; v to[i]; i nxt[i]) {if (f v) continue;//当Q1w[i]时此时Q2dp[u]-w[i]if (s1[v] w[i]) {//当Q2w[i]时此时Q2dp[u]-w[i]if (dp[u] - w[i] w[i]) dp[v] dp[u] - w[i] s1[v];//否则Q2w[i]else dp[v] w[i] s1[v];//叶子结点减去重复贡献if (in[v] 1) dp[v] - s1[v];}//当Q1s1[v]时此时Q2dp[u]-s1[v]else { //当Q2w[i]时此时Q2Q2if (dp[u] - s1[v] w[i]) dp[v] dp[u];//否则Q2w[i]else dp[v] w[i] s1[v];//叶子结点减去重复贡献if (in[v] 1) dp[v] - s1[v];}dfs2(u, v);}
}
int main()
{cin T;while (T--){//多组数据输入一定要记得初始化for (int i 1; i tot; i) to[i] nxt[i] w[i] 0;for (int i 1; i n; i) in[i] h[i] s1[i] dp[i] 0;tot 0;cin n;for (int i 1, a, b, c; i n; i) {scanf(%d%d%d, a, b, c);add(a, b, c); add(b, a, c);}int root 1;//找到非叶子结点作为第一次dfs的根for (int i 1; i n; i)if (in[i] ! 1) {root i; break;}dfs1(0, root);dp[root] s1[root];dfs2(0, root);long long ans 0;//找最大值for (int i 1; i n; i) ans max(ans, dp[i]);cout ans endl;}return 0;
}
