检测网站名 注册,红旗渠建设集团网站,在百度做网站销售,网站建设规划文档一.树上差分的基本概念
1.树上差分的定义
树上差分#xff0c;顾名思义#xff0c;意思就是在树上做差分。
至于什么是差分呢#xff1f;如果不会的同学#xff0c;可以先看看我的这篇博客:一维,二维差分の详解#xff08;简单易懂#xff09;_一维差分-CSDN博客
2.树…一.树上差分的基本概念
1.树上差分的定义
树上差分顾名思义意思就是在树上做差分。
至于什么是差分呢如果不会的同学可以先看看我的这篇博客:一维,二维差分の详解简单易懂_一维差分-CSDN博客
2.树上差分能解决的问题
树上差分有什么作用举个例子如果题目要求对树上的一段路径进行操作并询问某个点或某条边被经过的次数树上差分就可以派上用场了。
类比于差分数组,树上差分利用的思想也是前缀和思想。(在这里应该是子树和思想
树上差分就是利用差分的性质对路径上的重要节点进行修改而不是暴力全改作为其差分数组的值最后在求值时利用dfs遍历求出差分数组的前缀和得出答案就可以达到降低复杂度的目的。
树上差分时需要求LCA不会的同学可以先看看我的这篇博客:详解最近公共祖先(LCA)-CSDN博客
树上差分一般有两种类型的题目一种是对边进行差分另一种就是对点进行差分。
下面我将会分别讲解一下这两种问题。 二.点差分
1.思路
直接去dfs暴力加点权的话肯定会TLE,但是我们现在在讲啥?树上差分啊!
假设需要将两点u,v之间路径上的所有点权增加x,l是lca(u,v),p是l的父亲节点则差分操作如下
sum[u] x;
sum[v] x;
sum[l] - x;
sum[p] - x;
举个栗子(其中假设x1): 其中s和t就是题目中树上点权需要加1的节点的起始点绿色的数字代表点权(已经加1了)
则操作后有 至于为什么要这么操作呢?别急继续往下看。
做完上述的差分操作后我们就要统计答案了。
当我们dfs搜索到s向上回溯。
下面以u表示当前dfs搜索到的节点。
对于每个u统计它的子树大小(要用前缀和的思想记录每个点的点权了)顺着路径标起来。
(即sum[u] sum[son])
我们会发现第一次从s回溯到s与t的LCA时候,sum[LCA(s,t)] sum[son[LCA(s,t)]]
此时sum[LCA(s,t)]0(-110)。这时我们不禁会有一个疑问: 不是LCA(s,t)会被经过一次嘛,为什么是0!
别急,我们继续搜另一边。.
继续我们搜索到t,向上回溯。
依旧统计每个u的子树大小sum[u]sum[son]
再度回到LCA(s,t)依旧是sum[LCA(s,t)]sum[son[LCA(s,t)]]
这个时候 sum[LCA(s,t)]1 这就达到了我们要的效果 (是不是特别优秀φ(゜▽゜*)♪)
但是我们还要思考一个问题:万一我们再从LCA(s,t)向上回溯的时候使得其父亲节点的子树和为1怎么办?这样我们不就使得其父亲节点被多经过了一次?
其实很简单我们只需要在前面差分操作时将sum[fa[lca(s,t)]]-x就行了。
这样就达到了标记我们路径上的点的要求! 是否有一种恍然大悟的感觉呢? 2.例题Max flow
问题 参考代码
#includebits/stdc.h
using namespace std;
int n,q,mx[300001][41],deep[300001],sum[300001],ans;
vectorint vec[300001];
void dfs(int x,int fa)//lca的初始化
{deep[x] deep[fa] 1;mx[x][0] fa;for(int i 0;i vec[x].size();i)if(vec[x][i] ! fa)dfs(vec[x][i],x);
}
int lca(int x,int y)//倍增法求lca
{if(deep[x] deep[y]) swap(x,y);for(int i 40;i 0;i--)if(deep[mx[x][i]] deep[y])x mx[x][i];if(x y) return x;for(int i 40;i 0;i--)if(mx[x][i] ! mx[y][i]){x mx[x][i];y mx[y][i];}return mx[x][0];
}
void dfss(int x,int fa)//统计答案的最大值
{for(int i 0;i vec[x].size();i){int t vec[x][i];if(t fa) continue;dfss(t,x);sum[x] sum[t];//在树上进行类似于前缀和的操作}ans max(ans,sum[x]);//取最大值
}
signed main()
{cinnq;for(int i 1;i n;i){int u,v;scanf(%d%d,u,v);vec[u].push_back(v);vec[v].push_back(u);}dfs(1,0);for(int j 1;j 40;j)for(int i 1;i n;i)mx[i][j] mx[mx[i][j - 1]][j - 1];while(q--){int u,v;cinuv;int l lca(u,v);sum[u];//树上差分sum[v];sum[l]--;if(l ! 1) sum[mx[l][0]]--;//如果l有父节点就进行后面的操作}dfss(1,0);coutans;return 0;
} 三.边差分
1.思路
思想其实和点差分是一样的我来讲一下操作。
设将两点s,t之间路径上的所有边权增加xlLCA(s,t)以每条边两端深度较大的节点存储该边的差分数组则操作如下
sum[s] x;
sum[t] x;
sum[l] - 2 * x;
举个栗子(其中假设x1): 红色边为需要经过的边,绿色的数字代表经过次数。
但是由于我们不能储存边权所以只能把边权塞给了点权,因此我们的图应该是这样的 这样的话我们只要把sum[s],sum[t],sum[lca(s,t)]-2就可以实现差分操作了。
同样地只要dfs一遍遍历时统计以每个节点为根的树的节点的权值和就是当前节点到父亲节点的边的最终权值了 是不是很厉害
至于为什么点差分和边差分的操作不一样很简单请读者自己思考。
树上差分主要还是学习思想吧
2.例题树上必经边--边差分
问题 参考代码
#includebits/stdc.h
using namespace std;
int n,q,mx[300001][41],deep[300001],sum[300001],ans,k;
vectorint vec[300001];
void dfs(int x,int fa)
{deep[x] deep[fa] 1;mx[x][0] fa;for(int i 0;i vec[x].size();i)if(vec[x][i] ! fa)dfs(vec[x][i],x);
}
int lca(int x,int y)
{if(deep[x] deep[y]) swap(x,y);for(int i 40;i 0;i--)if(deep[mx[x][i]] deep[y])x mx[x][i];if(x y) return x;for(int i 40;i 0;i--)if(mx[x][i] ! mx[y][i]){x mx[x][i];y mx[y][i];}return mx[x][0];
}
void dfss(int x,int fa)
{for(int i 0;i vec[x].size();i){int t vec[x][i];if(t fa) continue;dfss(t,x);sum[x] sum[t];}
}
signed main()
{cinnqk;for(int i 1;i n;i){int u,v;scanf(%d%d,u,v);vec[u].push_back(v);vec[v].push_back(u);}dfs(1,0);for(int j 1;j 40;j)for(int i 1;i n;i)mx[i][j] mx[mx[i][j - 1]][j - 1];while(q--){int u,v;cinuv;int l lca(u,v);sum[u];sum[v];sum[l] - 2;}dfss(1,0);for(int i 2;i n;i)if(sum[i] k)ans;coutans;return 0;
} 四.BB in last
如果这篇博客对您有帮助的话别忘了点赞收藏加关注支持一下吖~(小声BB)(ov)ノ
