526互联

DSU on tree——从入门到入土

发布时间 2023-05-28 17:21:19作者: 铃狐sama

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最难，其他还好但状态设计很难想，时间复杂度高了）