首页 > 其他分享 >树上差分与LCA

树上差分与LCA

时间:2022-11-25 20:06:15浏览次数:81  
标签:include int fath 差分 fa LCA 树上 节点


树上差分与LCA

​可以看b站的这个视频​​讲的很不错强烈推荐

LCA

什么是LCA

LCA 全称 Least Common Ancester 即最近公共祖先

  • 祖先:从树根到当前节点的路径中经过的点(不包括当前节点,并且因为是树,所以路径唯一)
  • 公共祖先:两个节点祖先的交集部分的点
  • 最近公共祖先:两个节点的公共祖先中深度最大的那个点

如何求解LCA?

首先考虑两个深度一样的点
对于两个深度相同的点x,y 他们到LCA的深度差是相同的
那么我们可以采取x,y同时向上跳,直到跳到相同的节点。但是这样是低效的,可能会被卡成O(N)。

考虑使用倍增法来优化
假设LCA到x的距离为d,那么d一定可以表示成一个二进制数
只要给这个二进制树每一位赋0/1,找到最小的d即可,相当于让节点每次跳树上差分与LCA_深度学习

如何让节点每次跳树上差分与LCA_差分_02步?
我们可以倍增地记录当前节点的祖先,让树上差分与LCA_#include_03表示树上差分与LCA_#include_04树上差分与LCA_#include_05层的祖先是谁,可以得到递推式
树上差分与LCA_权值_06
树上差分与LCA_#include_07
那么我们只需要计算节点向上跳的最小深度d即可
我们在计算二进制数的时候从大往小枚举,所以我们也从大到小枚举j

如果树上差分与LCA_深度学习_08,有可能跳过LCA了,先不着急跳
如果树上差分与LCA_深度学习_09,还没跳过LCA了,直接跳上去
如果树上差分与LCA_深度学习_08,也可能就是LCA了,但我们没有跳上去,这时候直接返回父亲节点就可以了,因为最终还是会跳上去的

for(int j=20;j>=0;j--){
if(fa[x][j]!=fa[y][j]){
x=fa[x][j],y=fa[y][j];
}
return fa[x][0]
}

那么如果深度不同呢?
我们让深度大的节点跳到和深度小的节点深度一样的地方就可以了,依旧使用倍增类似倍增的方法,每次跳树上差分与LCA_#include_05。(其实就是拆分二进制嘛)

int LCA(int x,int y){
if(deep[x]>deep[y])swap(x,y);//令deep[x]<deep[y]
for(int i=t;i>=0;i--)
if(deep[fa[y][i]]>=deep[x])y=fa[y][i];//把x调到和y同深度
if(x==y)return x;
for(int i=t;i>=0;i--)//让x和y同时向上走2^i步数
if(fa[x][i]!=fa[y][i]){
x=fa[x][i],y=fa[y][i];
}
return fa[x][0];
}

做LCA之前先建树然后用dfs或者bfs把每个点的深度和父亲节点找出来

例题

洛谷 P3379 【模板】最近公共祖先(LCA)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<utility>
#include<set>
#include<vector>
#include<queue>
#include<stack>
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int>PII;
#define endl '\n'
//CHECK MULTIPLY INPUT !!!
//NEW DATA CLEAN !!!
//THINK > CODE !!!
const int N=5e5+10,M=25;
int fath[N][M],dep[N];
vector<int>root[N];
int n,m,s;
void dfs(int u,int fa){
fath[u][0]=fa;
dep[u]=dep[fa]+1;
for(auto v:root[u]){
if(v!=fa)dfs(v,u);
}
}
int LCA(int x,int y){
if(dep[x]<dep[y])swap(x,y);
while(dep[x]>dep[y])
x=fath[x][(int)log2(dep[x]-dep[y])];
if(x==y)return y;
for(int i=20;i>=0;i--){
if(fath[x][i]!=fath[y][i]){
x=fath[x][i],y=fath[y][i];
}
}
return fath[x][0];
}
int main(){
cin>>n>>m>>s;
for(int i=1;i<n;i++){
int x,y;cin>>x>>y;
root[x].push_back(y);
root[y].push_back(x);
}
dfs(s,0);
for(int j=1;j<=20;j++)
for(int i=1;i<=n;i++)
fath[i][j]=fath[fath[i][j-1]][j-1];
while(m--){
int x,y;cin>>x>>y;
cout<<LCA(x,y)<<endl;
}
return 0;
}

树上差分

按点差分

解决问题:把路径上的点都加上某个值,最后求每个点的权值

我们把路径拆成x-LCA,y-LCA
每一部分从下向上走
对于x-LCA部分,我们只需树上差分与LCA_#include_12
对于y-LCA部分,我们只需树上差分与LCA_深度学习_13
然后发现LCA被修改了两次,所以我们要对LCA取消一次重复的差分标记
树上差分与LCA_#include_14

综上

int lca=LCA(x,y);
mark[x]++,mark[y]++;
mark[lca]--,mark[fa[lca][0]]--;

最后每个点的权值就是它子树的mark值之和

按边差分

解决问题:把x到y的路径上的每一条边加上某值,最后求每条边的值

常见方法:边权化点权(边权下放)
每个节点最多只有一个父节点,也就是向上连的边只有一条
所以我们就把一条边的边权转化成子节点的点权(根节点没有点权)
这样就转化到点差分了
对于x-y的路径还是分成x-LCA和y-LCA上
但要注意LCA的权值不变

mark[x]++,mark[y]++,mark[LCA]-=2

最后每个点的权值就是它子树的mark值之和,然后在化回边权即可(预处理的时候把每个点对应的边记录一下)

按深度差分

解决问题:在x的子树中,修改深度为dep[x]~dep[x]+k的点

把有关x的修改都记录下来,搜到x的时候,依照每个修改打上差分标记即可。
注意处理k特别大的情况,改成<=n
最后记得回溯
流程大概是:记录修改-深搜节点-打差分标记-前缀和算答案-回溯把差分标记回复

CF1076E

在这里插入代码片


标签:include,int,fath,差分,fa,LCA,树上,节点
From: https://blog.51cto.com/u_15891800/5887697

相关文章

  • [NEFU ACM大一暑假集训 解题报告]前缀和与差分
    [NEFUACM大一暑假集训解题报告]前缀和与差分题量略大,所以解题报告和fjy大佬分了一下工由我负责A-K部分题解(不是AK部分题解啊,哈哈)后半部分题解(LM+R~V+XYZ)由fjy大佬发布......
  • 题解 LGP4211【[LNOI2014]LCA】
    problem一棵树,多次给定\(l,r,z\)询问\(\sum_{l\leqi\leqr}dep_{lca(i,z)}\),允许离线,\(n\leq50000\)。solution转换:这个\(dep_u\)的定义为\(u\)到根节点的点数......
  • ADPCM(自适应差分脉冲编码调制)的原理和计算
    关于ADPCMADPCM(AdaptiveDifferentialPulseCodeModulation,自适应差分脉冲编码调制)是一种音频信号数字化编码技术,音频压缩标准G.722,G.723,G.726中都会使用到......
  • 2022NOIP A层联测33 GCD 简单题 建筑 树上前缀和
    T1:[图论/枚举]给出有边权无向图,边权保证互不相同,Q次询问从S到T的路径中,边权的gcd最大是多少。(n<=1e4,Q<=2e5,w<=1e6)考场根据之前的一道图论题经验,在最短路上加个“\(w......
  • P3178 [HAOI2015]树上操作 的dfs序题解
    操作1:把某个节点x的点权增加a。操作2:把某个节点x为根的子树中所有点的点权都增加a。操作3:询问某个节点x到根的路径中所有点的点权和。//点修改+树修改,(点......
  • 【XSY3320】【LOJ6681】yww 与树上的回文串(border理论,点分治)
    咕了一年的题。先点分治。考虑某条经过当前重心\(rt\)的合法回文路径:(图摘自yww的题解)其中\(x\toy\)是合法回文路径,那么\(T\)是一个回文串。先把\(rt\)到每......
  • 树上差分
    title:树上差分date:2022-11-1510:30:06tags:算法本文章遵守知识共享协议CC-BY-NC-SA,转载时需要署名,推荐在我的个人博客阅读。树上点差分问题描述:给定一个有n......
  • 1732. 找到最高海拔 ----- 简单模拟、差分数组前缀和
    有一个自行车手打算进行一场公路骑行,这条路线总共由 n+1 个不同海拔的点组成。自行车手从海拔为0 的点 0 开始骑行。给你一个长度为n 的整数数组 gain ,其中g......
  • vulnhub靶场Trollcave
    0x000靶场描述Trollcave是一个易受攻击的VM,在Vulnhub和信息安全战争游戏的传统中。你从一个你一无所知的虚拟机开始-没有用户名,没有密码,只是你可以在网络上看到的东西......
  • 树上差分总结
    用途(差分)它可以维护多次对序列的一个区间加上一个数,并在最后询问某一位的数或是多次询问某一位的数。(总之修改操作一定要在查询操作之前)修改的时间复杂度是\(O(1)\),而......