DSU on tree——从入门到入土
1.dsu有什么用?
降低时间复杂度——nlogn
dsu的作用在于将时间复杂度降低,由n方到nlogn
举个例子:
给一棵根为1的树,每次询问某个子树内颜色有多少种。树有N个节点,询问有M次。颜色范围为
[1,N]的整数。
数据范围:
对于前三组数据,有1<=M<=N<=100。
而对于所有数据,有1<=M<=N<=1e5。
很显然我不可能每一个点开一个二维数组,一个代表他是什么,另一个代表他的状态赛
所以说,我只能用一个数组来全体统计,但这样的话,我一个节点全部清空一次不就是n方了吗(至于为什么要清空,原因在于兄弟节点之间可能会影响,我dfs统计了一个子树后,这个颜色数组如果不清空的话可能另一个被影响)
那咋办?
等死呗
假设点x有3个子节点,分别是 y1 、y2和y3,如果只考虑这三棵子树的答案与x这颗子树的答案,而暂时忽略更下层的节点的答案如何统计,我们可以想到一个偷懒的办法:先分别统计得到dp[y2]与dp[y3],然后统计得到dp[y1]之后不重置数组,继续遍历子树y2与y3,最后进行点x自身的统计。
那么这样y1就只找了一次
那么我们让y1最大化不就可以减少复杂度了吗?
那y1不就是重儿子吗?
那么只要我每一次最大的只跑一次,那不就nlogn了吗?
DSU有哪些题型
1.统计模型
1.定义(自认为):
这一类模型我叫做统计模型,题目通常是:找到某个子树下某变量的数量,这个变量通常是max/min/数量,大多是情况下都是某个有限制的数量,例如:某子树下深度为x的数量
2.做法:
这种情况下就很简单,很容易维护add和del,加点重链剖分就好了
模板代码如下
3.关键:
其中的关键在于:
1.dfs1函数,类似地进行重链剖分
2.add和del函数,用于对某一个点的贡献修改
3.rai和clear函数,用于对某个点及其子树的贡献修改
4.注意一下raise不能用作函数名,会GG
5.最重要的getans函数,用来满足dfu on tree,记忆的方法:get轻get重,加轻加重,统计删轻。
4.模板代码:
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
vector<int>mp[100005];
int cntdep[100005];
int dp[100005];
int sz[100005];
int dep[100005];
int dppos[100005];
int dfn[100005];
int rev[100005];
int father[100005][20];
int times;
int ans[100005];
struct node{
int p;
int id;
};
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
void write(int x)
{
if(x<0)
putchar('-'),x=-x;
if(x>9)
write(x/10);
putchar(x%10+'0');
return;
}
vector<node>q[100005];
void dfs1(int x,int fa){
dfn[x]=++times;
rev[dfn[x]]=x;
dep[x]=dep[fa]+1;
sz[x]=1;
for(int i=1;i<=18;i++){
father[x][i]=father[father[x][i-1]][i-1];
}
int ma=-1;
for(int i=0;i<mp[x].size();i++){
int to=mp[x][i];
if(to==fa){
continue;
}
dfs1(to,x);
sz[x]+=sz[to];
if(mp[x][0]==fa||ma<sz[to]){
ma=sz[to];
swap(mp[x][0],mp[x][i]);
}
}
}
int findfather(int x,int y){//找x的第y级祖先
for(int i=18;i>=0;i--){
if(y>=(1<<i)){
y-=(1<<i);
x=father[x][i];
}
}
return x;
}
void add(int x){
cntdep[dep[x]]++;
}
void del(int x){
cntdep[dep[x]]--;
}
void rai(int x){
for(int i=dfn[x];i<=dfn[x]+sz[x]-1;i++){
add(rev[i]);
}
}
void clear(int x){
for(int i=dfn[x];i<=dfn[x]+sz[x]-1;i++){
del(rev[i]);
}
}
void getans(int x,int fa,bool hvs){
for(int i=1;i<mp[x].size();i++){
int to=mp[x][i];
if(to==fa){
continue;
}
getans(to,x,0);
}
if(mp[x][0]!=fa){
getans(mp[x][0],x,1);
}
for(int i=1;i<mp[x].size();i++){
int to=mp[x][i];
if(to==fa){
continue;
}
rai(to);
}
add(x);
for(int i=0;i<q[x].size();i++){
ans[q[x][i].id]=cntdep[dep[x]+q[x][i].p];
}
if(!hvs){
clear(x);
}
}
int main(){
int n;
n=read();
int root;
for(int i=1;i<=n;i++){
int a;
a=read();
father[i][0]=a;
mp[a].push_back(i);
mp[i].push_back(a);
}
for(int i=1;i<=n;i++){
if(!father[i][0]){//找过了的话,dep肯定是有值的
dfs1(i,0);
}
}
// for(int i=1;i<=n;i++){
// cout<<mp[i][0]<<endl;
// }
int m;
m=read();
for(int i=1;i<=m;i++){
int v,p;
v=read();
p=read();
int pre=findfather(v,p);
// cout<<pre<<endl;
if(pre){//反正剩下的定义0
q[pre].push_back((node){p,i});
}
}
for(int i=1;i<=n;i++){
if(father[i][0]==0){
getans(i,0,0);
}
}
for(int i=1;i<=m;i++){
write(max(ans[i]-1,0));
printf(" ");
}
}
5.练习:
U41492 树上数颜色 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn):cnt数组统计颜色,达到1的话,ans+1即可,删除就反着做
Blood Cousins - 洛谷 | 计算机科学教育新生态 (luogu.com.cn):将深度视为颜色维护,这种将xx视为颜色的想法十分常见
Lomsat gelral - 洛谷 | 计算机科学教育新生态 (luogu.com.cn):这道题就是全局变量设一个max,在add时维护,clear时清零,然后统计即可,这种max一定不能到某个点了全部找状态数组一次看max,正确性肯定是的,但时间不优
Tree and Queries - 洛谷 | 计算机科学教育新生态 (luogu.com.cn):首先像这种离线处理的题(多个问题)还是很多的,应对方法就是每次统计到某个点时就看它挂载的问题,然后解决;其次这道题就相当于给cnt数组套了一个cnt1,求cnt1,维护同理。
Dominant Indices - 洛谷 | 计算机科学教育新生态 (luogu.com.cn):这道题就相当于第三题和第二题(比第二题简单点,不用LCA)的结合版,还是视dep为颜色,即求cnt【dep】的max,只要上面会,这个肯定没问题的
尤其小心n=1的坑哦,下一题也一样(不然re)
Tree Requests - 洛谷 | 计算机科学教育新生态 (luogu.com.cn):就相当于第二题(无LCA)的一个变式,你要知道的不仅是某一深度下有多少个点,更要知道这个深度下的a-z字符各有多少个,很明显,都为2的倍数就yes,否则no
Russian Dolls on the Christmas Tree(lg上没找到):这一道题一样的,就是维护有多少个“段”,稍微分一下类即可
联合模型
1.定义(自认为):
联合模型我理解为一个点x下,来自其不同分支的两个点u,v的条件关系的维护(x=LCA(u,v))
什么叫条件关系的维护?
直接说有点难受,我拿下面几个题来看
1.strange memory:Problem - F - Codeforces
这个的条件关系就是要求满足aLCA(i,j)=a(i) xor a(j);,寻找满足这样关系的i xor j的和
2.XOR TreeProblem - 1709E - Codeforces
这个的条件关系就是要求以所有简单路径xor不为0,最终求割裂出满足条件的最小次数
3.Tea TreeProblem - 1709E - Codeforces
这个的条件关系就是要满足gcd,然后找到每个点的max gcd
2.做法:
其实相对于上一种情况,就是每合并一次轻子树(加轻),就查找有没有已经满足了条件了的,然后统计答案(如果满足的话)
3.关键:
关键是在于时间…,我必须要求查找满足条件的答案的那一步时间较少(100左右),因此状态的设计要求很高
4.模板代码:
这个代码时第三题的代码,看到find就是关键步骤,而为了减少时间复杂度,状态设计为“是否有某个因子”,也就是app数组;
然后在getans中,合并轻子树前统计一次答案(你看,我先写的res=….,再用的rai)
inline void add(int x){
for(int i=0;i<d[col[x]].size();i++){//现在我加入了一个点,我要把这个点的权值的所有因子合并到父节点上去
int tt=d[col[x]][i];
app[tt]++;//表示有这个因子
}
}
inline void del(int x){
for(int i=0;i<d[col[x]].size();i++){//上一个反过来
int tt=d[col[x]][i];
app[tt]--;
}
}
inline void rai(int x){
for(int i=dfn[x];i<=dfn[x]+sz[x]-1;i++){
add(rev[i]);
}
}
inline void clear(int x){
for(int i=dfn[x];i<=dfn[x]+sz[x]-1;i++){
del(rev[i]);
}
}
int find(int val){
for(int i=0;i<d[val].size();i++){
int x=d[val][i];
if(app[x]){
return x;
}
}
return -1;
}
inline void getans(int x,int fa,bool hvs){
for(int i=1;i<mp[x].size();i++){
int to=mp[x][i];
if(to==fa){
continue;
}
getans(to,x,0);
}
if(mp[x][0]!=fa){
getans(mp[x][0],x,1);
}
int res=-1;
for(int i=1;i<mp[x].size();i++){
int to=mp[x][i];
if(to==fa){
continue;
}
for(int i=dfn[to];i<=dfn[to]+sz[to]-1;i++){
res=max(res,find(col[rev[i]]));
}
rai(to);
}
res=max(res,find(col[x]));
add(x);
dp[x]=res;
if(!hvs){
clear(x);
}
}
习题:
Tea TreeProblem - 1709E - Codeforces
XOR TreeProblem - 1709E - Codeforces
strange memory:Problem - F - Codeforces
至于具体的代码实现就不放出来了,太难了(个人觉得xor tree最难,其他还好但状态设计很难想,时间复杂度高了)