点分治点分树学习随笔
点分治点分树学习随笔
0 前言
本蒟蒻看这个点分树模板看了3天才看懂
十分气愤
于是决定写点分治和点分树的学习随笔巩固一下
1点分治
1.1引入
思考：如何统计树上满足某条件的路径数量
比如：求树上满足u到v最短路径长度小于等于k的二元组（u,v）数量
显然，如果我们直接暴力搜索复杂度\(O(n^3)\)
那样我们不就直接T飞了吗！！！
所以我们需要惊人的注意力来优化一下这个东西
对于二元组，我们很自然地想到可以先提前处理出一个点造出的贡献
最后加在一起就可以了
那么怎么处理呢？
1.2做法
1.2.1问题转化
对于一个根节点u，对于u的子树，我们可以将路径分为两类：
- 过u
- 不过u
这样分有什么用呢？
as we all know 通过dfs我们可以将树上每一个点扫到
所以对于类型2我们可以在继续向下dfs时将其转化为类型1
那么类型1又该怎么办呢？
我们画一棵树来观察一下
(博客园咋给图片吞这么小了，在新标签页中打开图像看吧)
经过u的路径长度
\(dis(x,y)=dis(x,u)+dis(y,u)\)
比如图中过u的合法路径是：(只看s1,s2,s3)
s1->u->s2(4+7=11)，s1->u->s3(4+6=10)
s1->u(4+0=4)，s2->u(7+0=7)，s3->u(6+0=6)
（直接到根节点也是可以的）
那么我们就将问题转化为： 求二元组（x,y）满足\(dis(x,u)+dis(y,u)<=k\)且\(b[x]!=b[y]\)的数量
d[i]=dis(i,u) i到根节点u的距离
b[i]=(i属于u的哪一个子树s1/s2/s3...)
这两个东西我们可以提前dfs预处理出来
为什么是\(b[x]!=b[y]\)？
还是上面的图 如果我们将k改为20
不加上这个条件我们x->u->x,x->u->fa[x],x->u->s1就都为u所能产生的合法路径
但是这些都不是最短路径，所以我们需要舍去
1.2.2答案统计优化
那么又有人问了：主播主播 你这里枚举d[i]不还是\(O(n^2)\)吗？
别慌 我们已经转化成了如此精美的东西
那么用上一点神奇的小优化就可以了
看这个东西：\(dis(x,u)+dis(y,u)<=k\)
就是我们预处理出的d[x]+d[y]<=k
还看不出来什么的话我们先给这些d[i]排个序
现在是不是有点双指针的感觉了？
那么我们将所有点按d[i]排序
设双指针区间是[L,R]
若d[L]+d[R]<=k,说明L可以和L+1到R间所有长度匹配
ans+=R-L
然后L++ ,操作R直到满足上面的条件
但是我们不想要在同一子树内的长度
于是维护cnt[b[L]]
表示当前双指针区间内和L在同一子树内的点
这个很好维护，一开始cnt[b[i]]都++
然后在操作L，R时对应加减cnt即可
最后就变成了ans+=R-L-cnt[b[L]]
那么我们直接就干掉了一个\(O(n)\)
现在的一个子树的处理复杂度来到了惊人的 \(O(n+log n)\)=\(O(n)\)
1.2.3重心
点分治还有另一个重要操作 找重心
1.2.3.1定义
重心是啥？
和物理中的定义差不多
就是物体的几何中心（我瞎说的 权威的看这里 ）
而OI里面树上的重心又是啥呢
其实就是自己子树最大大小最小的点
（有点复杂 断个句：子树的最大大小/最小的点）
1.2.3.2用处
为什么要用这个重心呢？
先看我们现在的复杂度
我们现在是一个点一个点地处理 处理完后就将这个点删去
我们一次操作的复杂度是\(O(n)\)对吧
如果要让我们的代码不T飞 最后的时间复杂度肯定小于\(O(n^2)\)
那肯定就是带log的
由于每次到找的重心 它的每个子树大小最大都为当前大小的一半
所以使用重心递归会使递归层数变为\(O(logn)\)
于是我们就用重心去优化我们分治时的层数
画个图理解一下：
假如说我们以U为根向下扫
一共是114514+3个点
然后继续向下处理子树（相当于直接删掉U这个点）
那么剩下的就是 S1 以及 S2和S2的子树
S1这个区块只有一个点，但是S2区块点数达到惊人的114514+1个点
我们在处理S2区块的时候复杂度就和处理S1差不多了
我们如果每次找的根都出现这种情况
最后的复杂度直接退化到了\(O(n^2)\)
所以
我们每一次以当前查询区块的重心作为根节点向下扫
预处理出当前区块所有点子树大小和当前点下最大子树大小
最后找出最大子树大小最小的点作为根节点继续分治即可
这一步放dfs里面一起预处理一下丝毫不影响时间复杂度
所以最后的复杂度就是\(O(nlogn)\)
1.3模板代码
最后附上猎奇重口的模板代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=40005;
const int INF=0x3f3f3f3f;
int n,k;
int aa,bb,cc;
struct node{
int v,w;
};
vector<node> child[N];
void add(int a,int b,int c){
child[a].push_back({b,c});
child[b].push_back({a,c});
}
int dep[N];//深度
int dd[N];//到根节点距离
int vis[N];//被分治过没
node dis[N];//存所有距离
int cnt;
int root;
int Max[N];//该节点下最大子树大小
int siz[N];//子树大小
int Ans;//最后答案
int s;//当前子树大小
int cn[N];//cnt 容斥
int b[N];//u下哪一个子树
int q[N];
int p=0;
bool cmp(node x,node y){
return x.w<y.w;
}
void getroot(int u,int fa){//dfs+找重心
siz[u]=1;
Max[u]=0;
for(auto to:child[u]){
int v=to.v;
int w=to.w;
if(v==fa||vis[v])continue;
getroot(v,u);
siz[u]+=siz[v];
Max[u]=max(Max[u],siz[v]);
}
Max[u]=max(Max[u],s-Max[u]);
if(Max[u]<Max[root]){
root=u;
}
}
void getdeep(int u,int fa){//找所有距离
dis[++cnt]={u,dd[u]};
if(dep[u]>1){
b[u]=b[fa];
}else if(dep[u]==1){
b[u]=u;
}
for(auto to:child[u]){
int v=to.v;
int w=to.w;
if(vis[v]||v==fa)continue;
dd[v]=dd[u]+w;
dep[v]=dep[u]+1;
getdeep(v,u);
}
return;
}
int getans(int u){//找经过当前点答案
dd[u]=dep[u]=s=0;
p=0;
cnt=0;
b[u]=0;
getdeep(u,0);
sort(dis+1,dis+cnt+1,cmp);
memset(cn,0,sizeof(cn));
int l=1,r=cnt,ans=0;
for(int i=2;i<=cnt;i++){
cn[b[dis[i].v]]++;
}
while(l<r){
if(dis[l].w+dis[r].w<=k){
ans+=r-l-cn[b[dis[l].v]];
l++;
cn[b[dis[l].v]]--;
}else{
cn[b[dis[r].v]]--;
r--;
}
}
return ans;
}
void divide(int u){//分治
vis[u]=1;
b[u]=u;
Ans+=getans(u);
memset(dep,0,sizeof(dep));
memset(dd,0,sizeof(dd));
for(auto to:child[u]){
int v=to.v;
int w=to.w;
if(vis[v])continue;
s=siz[v];
Max[root=0]=INF;
getroot(v,0);
divide(root);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<n;i++){
cin>>aa>>bb>>cc;
add(aa,bb,cc);
}
cin>>k;
s=n;
Max[root=0]=INF;
getroot(1,0);
getroot(root,0);
divide(root);
cout<<Ans<<endl;
}
完结撒花！！！
2点分树
2.1引入
假如说我们在上面点分治的基础上再加上一个修改和查询的操作会怎么样？
那每查询一次跑一遍复杂度直接来到了\(O(n^2logn)\)！！！又被T飞了
2.2做法
怎么优化？
我们肯定需要使用神奇优化
2.2.1分析
那么我们寻找一下这里\(O(n^2logn)\)到底是啥东西拖了后腿
一个\(n\)是分治找重心，一个\(logn\)是分治的深度，一个\(n\)是双指针统计当前点答案，
能优化啥？
分治的深度已经非常好了 不能再少了
答案的统计也少不了了
那么问题肯定处在找重心上：
我们发现找重心的依据是什么呢？
重心是根据原树上的子树大小来定的
也就是说我们修改点权后并不会影响原树上的父子关系
自然也不会影响重心的分布
2.2.2预处理优化
既然每一次修改点权后重心分布不会改变
那么我们就预处理一下重心们的父子关系
相当于重开了一棵树
点分树的名字应该就是这么来的
这样我们就不用每一次都找重心了
直接用我们找出来的重心树去搜索即可
那么我们又优化掉了一个\(O(n)\)！！！
注意：这里由于我们搜索的方式变了
最后统计答案的方式也会有所改变
2.2.3统计答案
2.2.3.1 think
这里借助板子题理解一下震波
think think
我们需要维护些什么信息？
- 原树父子关系
- 原树点权
- 当前点权
- 点分树（重心父子关系）
但是！
由于我们是在点分树上统计的答案
所以我们并不能快速地通过原来的查找方式去统计答案
为什么？
点分治的ask是单次的 而且我们上面的询问是问的整棵树
并没有问哪一个具体的点
而点分树要问一个具体的点
到这个点的距离小于等于k的点权和，如何快速统计这个呢
再think一下
每一个点在点分树上一直往上跳肯定最终跳到整棵树的那个中心上
而我们需要查询的点也正是它跳上去所经过的这些点的答案总和
那么现在\(O(logn)\)的跳转，剩下一个单点答案查询
又有前缀和，又有最大值限制，最大值还小于1e5（原树成链了最大距离才1e5-1）
那么我们直接上树状数组
定义对于每个重心\(u\)，\(T[0][u][s]\)表示所有属于\(u\)管辖范围内的节点，过\(u\)路径距离长度等于\(s\)的点权总和
but
我们很快就发现不对劲了
点分治的时候提到过 会存在起点终点在同一子树内的情况
怎么办呢？
再开一个！
依旧对于每个重心\(u\)，定义 \(T[1][u][s]\)表示
对于点\(u\)管理的范围内
过\(u\)且起点终点在同一子树内的路径长度等于\(s\)的点权和
最后查询时用\(T0\)减去\(T1\)即可
2.2.3.2处理
这里十分巧妙，主播也是在这里被硬控了几个小时。。。
update
和查询一样 影响的点只会是点分树上的一堆fa
所以每次add变化量到T0,T1上去就好了
add在T0上的该怎么加就怎么加
从自己到重心的距离开始加，加到最大距离
T1呢，这里如果扫到的是\(u\)，加的应该就是\(u\)在点分树上fa的T1
为什么？
画图！
发现 当前扫的是过u的对吧
那么我们可以处理出对u自己子树内的贡献
而这个贡献恰巧是我们fa[u]T1中的一部分
所以把add变化值到fa[u]中即可
2.2.4代码
说这么多还是直接看代码吧
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
const int MAXN=35;
const int INF=0x3f3f3f3f3f;
int n,m;
int B[N];//原树权
int A[N];//当前权
vector<int> child[N];//原树邻接表
int root;
int dep[N];//u的祖先重心层数
int vis[N];//标记是否分治过
int fa[N][MAXN];//fa[u][i] -> u第i个祖先重心
int dis[N][MAXN]; //dis[u][i] -> u到fa[u][i]的距离
int ma[N];//子树最大大小
int siz[N];//子树大小
vector<int> T[2][N]; //开vector防爆
void ADD(int x,int y){
child[x].push_back(y);
child[y].push_back(x);
return;
}
void getroot(int u,int f,int sum){
ma[u]=0;
siz[u]=1;
for(auto v:child[u]){
if(v==f||vis[v])continue;
getroot(v,u,sum);
siz[u]+=siz[v];
ma[u]=max(ma[u],siz[v]);
}
ma[u]=max(ma[u],sum-siz[u]);
if(root==0||ma[u]<ma[root]){
root=u;
}
return;
}
void getdis(int u,int f,int k,int d){
dep[u]++;
fa[u][dep[u]]=k;
dis[u][dep[u]]=d;
siz[u]=1;
for(auto v:child[u]){
if(v==f||vis[v])continue;
getdis(v,u,k,d+1);
siz[u]+=siz[v];//分配内存用
}
return;
}
int lowbit(int b){return b&(-b);}
void add(int u,int v,int f,int id){//修改到当前重心距离为u的点对整个距离的贡献值
for(int x=u;x<T[id][f].size();x+=lowbit(x)){//从到fa的距离->最大的到其他点的距离(最大距离不可能超过自己整个子树大小）
T[id][f][x]+=v;
}
return;
}
int qsum(int u,int f,int id){//查询距离为u内f点的贡献
int res=0;
for(int x=u;x;x-=lowbit(x)){
res+=T[id][f][x];
// cout<<res<<endl;
}
return res;
}
void maindfs(int u){//对于u进行dfs
vis[u]=1;
getdis(u,0,u,0);
T[0][u].resize(siz[u]+5);
T[1][u].resize(siz[u]+5);
for(auto v:child[u]){
if(vis[v])continue;
root=0;
getroot(v,0,siz[v]);
maindfs(root);
}
return;
}
void update(int u,int k){//将u点权修改为k
for(int i=dep[u];i;i--){
int f=fa[u][i];
add(dis[u][i]+1,k-A[u],f,0);//自己的T0 -> 在自己下面所有造成贡献点权和
if(i>1)add(dis[u][i-1]+1,k-A[u],f,1);//自己对于father的T1 -> 处理自己father在自己内重复计算的值
}
}
int fans(int u,int k){//查询的点 距离
int dd,res=0;
for(int i=dep[u];i;i--){
int f=fa[u][i];
int f1=fa[u][i+1];
int df=dis[u][i];
if(df<=k){
dd=T[0][f].size()-1;
dd=min(dd,k-df+1);
res+=qsum(dd,f,0);
if(f1){
dd=T[1][f1].size()-1;
dd=min(dd,k-df+1);
res-=qsum(dd,f1,1);
}
}
}
return res;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
int ans=0;
for(int i=1;i<=n;i++){
cin>>B[i];
A[i]=0;
}
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
ADD(a,b);
}
ma[root=0]=INF;
getroot(1,0,n);
maindfs(root);
for(int i=1;i<=n;i++){
update(i,B[i]);
A[i]=B[i];
}
while(m--){
int a,b,c;
cin>>a>>b>>c;
b^=ans,c^=ans;
if(a==1){
update(b,c);
A[b]=c;
}else{
ans=fans(b,c);
cout<<ans<<endl;
}
}
return 0;
}
完结撒花！🎉🎉🎉
浙公网安备 33010602011771号