从启发式合并到Dsu on Tree

传统启发式合并

[HNOI2009] 梦幻布丁

题目描述

nn 个布丁摆成一行，进行 mm 次操作。每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。

例如，颜色分别为 1,2,2,11,2,2,1 的四个布丁一共有 33 段颜色.

输入格式

第一行是两个整数，分别表示布丁个数 nn 和操作次数 mm。
第二行有 nn 个整数，第 ii 个整数表示第 ii 个布丁的颜色 aia_i。
接下来 mm 行，每行描述一次操作。每行首先有一个整数 opop 表示操作类型：

  • 若 op=1op = 1，则后有两个整数 x,yx, y，表示将颜色 xx 的布丁全部变成颜色 yy。
  • 若 op=2op = 2，则表示一次询问。

Sol：考虑初始答案就是看每一个数和自己前面的数是不是一样,算的时候多算n+1的目的是不需要特判处理边界，影响是答案固定需要减1。考虑合并过程，我们希望最后颜色是对的，所以我们保证x是小集合，向y这个大集合合并，但这样只会改变位置，不会改变位置对应的颜色。所以我们需要用modify函数维护位置的颜色，减去原颜色对答案的贡献，增加新颜色对答案的贡献。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//首先考虑统计段数，看与后面的数相同吗，不相同就多一段
//发现答案是和布丁具体颜色无关，只和种类个数有关
vector<int>pos[M-5];
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
	cin>>a[i];
	pos[a[i]].push_back(i);
	
    }
	int ans=0;
	//方便处理边界，答案固定-1.
	for(int i=1;i<=n+1;i++){
		if(a[i]!=a[i-1])ans++;
	}
	for(int i=1;i<=m;i++){
		int op;cin>>op;
		if(op==2)cout<<ans-1<<endl;
		else {
			int x,y;cin>>x>>y;
			if(x==y)continue;
			if(pos[x].size()>pos[y].size())pos[x].swap(pos[y]);
			if(pos[y].empty())continue;
			int col=a[pos[y][0]];
			auto modify=[&](int p,int col){
				ans-=(a[p]!=a[p+1])+(a[p]!=a[p-1]);
				a[p]=col;
				ans+=(a[p]!=a[p+1])+(a[p]!=a[p-1]);
			};
			for(auto z:pos[x]){
				modify(z,col);
				pos[y].push_back(z);
			}
			pos[x].clear();
		}
	}
}
=

启发式合并维护查询

【题解】金牌导航 启发式合并-连通性询问 - linyihdfj - 博客园 (cnblogs.com)

启发式合并,DSU on Tree - nannandbk - 博客园 (cnblogs.com)

启发式分治 https://hydro.ac/d/bzoj/p/4059

题意：一个序列被称为是不无聊的，仅当它的每个连续子序列存在一个独一无二的数字，即每个子序列里至少存在一个数字只出现一次。现在给定一个整数序列，请你判断它是不是不无聊的。

Sol：考虑一个性质，如果一个数在当前序列只出现一次，那么包含这个数的区间都是合法的，再考虑分治解决左右区间不包含这个数的部分。利用双指针完成启发式分治，谁先找到就递归哪边。判定条件是利用map维护nxt和pre数组的位置。

debug：注意vector的resize不会清空，只会补充元素，所以要先clear

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
int n,m;
int a[N];
vector<int>pre,nxt;
//启发式分治
//任意一个子区间，都存在一个数只出现了一次
//分析：先找到初始序列中只出现一次的数，那包含这个数的区间一定没问题
//因此我们只需要以此为分界，解决其左右区间的子问题
//对于一个区间来说，检查一个元素在[L,R]出现一次，记录上一处出现的位置和下一次出现的位置
/*
直接常规分治不对，比如出现一次的数都在一侧，这样子会分治层数会O(n)，我们希望log
T(n)=T(x)+T(n-x)+O(min(x,n-x))当分治的代价只和短的那一边有关，就要想起来这个了
这个复杂度的等式是和启发式合并的意义是相同的，所以nlogn
*/
bool cal(int l,int r){
	if(l>r)return true;
	for(int pl=l,pr=r;pl<=pr;pl++,pr--){
		if(pre[pl]<l&&nxt[pl]>r)return cal(l,pl-1)&&cal(pl+1,r);
		if(pre[pr]<l&&nxt[pr]>r)return cal(l,pr-1)&&cal(pr+1,r);
	}
	return false;
}
void solve(){
      cin>>n;
      pre.clear();nxt.clear();
      pre.resize(n+1);
      nxt.resize(n+1);
      
      for(int i=1;i<=n;i++)cin>>a[i];
      
      map<int,int>mp;
      for(int i=1;i<=n;i++){
      	if(mp.count(a[i])){
      		pre[i]=mp[a[i]];
      	
		  }
		  else pre[i]=0;
		mp[a[i]]=i;
	  }
	  mp.clear();
	  for(int i=n;i>=1;i--){
	  	   if(mp.count(a[i])){
	  	   	    nxt[i]=mp[a[i]];
			}
			else nxt[i]=n+1;
			mp[a[i]]=i;
	  }
	  bool flag=cal(1,n);
	  if(flag)cout<<"non-boring"<<endl;
	  else cout<<"boring"<<endl;
}

树上启发式合并

1.解决子树问题

  • 只支持子树查询
  • 不支持修改操作

Luogu CF1709E XOR Tree

给定一棵树，点带点权，问：最少多少次修改使得树上任意一条简单路径的点权异或和不为0。

Sol：我们只考虑在每条路径的lca处理，这也是树形dp常见的处理出发点。考虑钦定1为根，然后预处理树上异或前缀和d。考虑如果u和v之间存在非法路径，则d[u]⊕d[v]⊕a[lca]d[u]\oplus d[v] \oplus a[lca]==0 .考虑子树合并的过程中，我们给每个节点维护set，当我们合并子树的时候，我们采用启发式合并，保证合并次数的复杂度是O(nlogn)O(nlogn)，由于需要用set维护，每次合并的时候复杂度是O(logn)O(logn),总时间复杂度是O(nlogn2)O(nlogn^2)

考虑具体修改方案，我们只需要修改lca处的点权值改成很大，保证异或的时候高位的1消除不掉即可，所有经过lca的非法路径都将不复存在。

代码使用递归实现，常数较大，且本题使用的是set的启发式合并。后面代码将展示使用dfs序和重儿子优先的方式来减小常数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int a[N];
vector<int>e[N];
set<int>s[N];
int d[N];
int ans=0;
void dfs(int u,int fa){
	bool flag=false;
	s[u].insert(d[u]);
	for(auto v:e[u]){
		if(v==fa)continue;
		d[v]=d[u]^a[v];
		dfs(v,u);
        if(s[u].size()<s[v].size())swap(s[u],s[v]);
		for(auto z:s[v]){
			int tmp=z^a[u];
			if(s[u].find(tmp)!=s[u].end())flag=true;
			//不能边查询边合并啊，要全部先查完再合并子树
			//s[u].insert(z)//这句代码就是典型的错误
		}
		for(auto z:s[v])s[u].insert(z);
	
	}
	if(flag){ans++;s[u].clear();}
}
void solve(){
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n-1;i++){
        	int u,v;cin>>u>>v;
        	e[u].push_back(v);
        	e[v].push_back(u);
        }
        d[1]=a[1];
       
        
        dfs(1,0);
        cout<<ans<<endl;
}

Lomsat gelral题面：

  • 有一棵 nn 个结点的以 11 号结点为根的有根树。

  • 每个结点都有一个颜色，颜色是以编号表示的， ii 号结点的颜色编号为 cic_i。

  • 如果一种颜色在以 xx 为根的子树内出现次数最多，称其在以 xx 为根的子树中占主导地位。显然，同一子树中可能有多种颜色占主导地位。

  • 你的任务是对于每一个 i∈[1,n]i\in[1,n]，求出以 ii 为根的子树中，占主导地位的颜色的编号和。

  • n≤105,ci≤nn\le 10^5,c_i\le n

Sol:考虑使用dsu on tree,每次先递归得到轻儿子答案，同时删除影响。再递归重儿子，保留贡献。二次递归轻儿子合并子树计算贡献。为什么不开O(n)个map去存储答案，从空间和时间上来说都非常差，所以我们考虑用一个数组原地修改，维护的答案及时清空。

递归版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
vector<int>e[N];
int sz[N];
int son[N];
int sum=0,mx=0;
int cnt[N];
int col[N];
int ans[N];
void dfs1(int u,int fa){
	sz[u]=1;
	for(auto v:e[u]){
		if(v==fa)continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[v]>sz[son[u]])son[u]=v;
	}
}
void add(int u,int fa,int hs){
	cnt[col[u]]++;
	if(cnt[col[u]]>mx){
		mx=cnt[col[u]];
		sum=col[u];
	}
	else if(cnt[col[u]]==mx)sum+=col[u];
	for(auto v:e[u]){
		if(v==fa||v==hs)continue;
		add(v,u,hs);
	}
}
void sub(int u,int fa){
	cnt[col[u]]--;
	for(auto v:e[u]){
		if(v==fa)continue;
		sub(v,u);
	}
}
void dfs2(int u,int fa,int op){
	for(auto v:e[u]){
		if(v==fa||v==son[u])continue;
		dfs2(v,u,0);
	}
	if(son[u])dfs2(son[u],u,1);
	add(u,fa,son[u]);
	ans[u]=sum;
	if(op==0){
		sub(u,fa);
		sum=mx=0;
	}
}
void solve(){
     cin>>n;
     for(int i=1;i<=n;i++)cin>>col[i];
     for(int i=1;i<=n-1;i++){
     	int u,v;cin>>u>>v;
     	e[u].push_back(v);
     	e[v].push_back(u);
     }
     dfs1(1,0);
     dfs2(1,0,0);
     for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
}

dfs序优化常数版本:在合并轻儿子的子树过程中，直接利用dfs序for循环遍历所有节点进行答案更新，这样的方法和递归相比L虽然都是线性，但是for肯定快于递归的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
vector<int>e[N];
int sz[N];int son[N];
int sum=0,mx=0;
int cnt[N];int col[N];
int ans[N];
int l[N];int r[N];int tot=0;int id[N];
//预处理dfs序和重儿子
void dfs1(int u,int fa){
	l[u]=++tot;
	id[tot]=u;
	sz[u]=1;
	for(auto v:e[u]){
		if(v==fa)continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[v]>sz[son[u]])son[u]=v;
	}
	r[u]=tot;
}
//统计答案
void dfs2(int u,int fa,int op){
	for(auto v:e[u]){
		if(v==fa||v==son[u])continue;
		dfs2(v,u,0);
	}
	//先递归到轻儿子
	if(son[u])dfs2(son[u],u,1);
	//计算重儿子
	auto add=[&](int x){
		int cur=col[x];
		cnt[cur]++;
		if(cnt[cur]>mx){
			mx=cnt[cur];
			sum=cur;
		}
		else if(cnt[cur]==mx)sum+=cur;
	};
	auto del=[&](int x){
		int cur=col[x];
		cnt[cur]--;
	};
	//合并轻儿子的子树
	for(auto v:e[u]){
		if(v==fa||v==son[u] )continue;
		for(int i=l[v];i<=r[v];i++)add(id[i]);
	}
	//当前根节点本身
	add(u);
	ans[u]=sum;
	if(op==0){
		//清空贡献
		sum=0;mx=0;
		for(int i=l[u];i<=r[u];i++)del(id[i]);
	}
}
void solve(){
     cin>>n;
     for(int i=1;i<=n;i++)cin>>col[i];
     for(int i=1;i<=n-1;i++){
     	int u,v;cin>>u>>v;
     	e[u].push_back(v);
     	e[v].push_back(u);
     }
     dfs1(1,0);
     dfs2(1,0,0);
     for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
}

U41492 树上数颜色 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

给一棵根为1的树，每次询问子树颜色种类数

Sol:合并子树的时候维护一个桶，每次有新颜色出现的时候答案加1。清除操作的时候答案清0，对应颜色的桶减1即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
int col[N];int cnt[N];
int sum=0;int ans[N];
vector<int>e[N];
int son[N];int sz[N];
int l[M],r[N],tot=0;int id[N];
void dfs1(int u,int fa){
	sz[u]=1;
	l[u]=++tot;
	id[tot]=u;
	for(auto v:e[u]){
		if(v==fa)continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[son[u]]<sz[v])son[u]=v;
	}
	r[u]=tot;
}
void dfs2(int u,int fa,int op){
	for(auto v:e[u]){
		if(v==fa||v==son[u])continue;
		dfs2(v,u,0);
	}
	if(son[u])dfs2(son[u],u,1);
	auto add=[&](int x){
		int cur=col[x];
		if(cnt[cur]==0)sum++;
		cnt[cur]++;
	};
	auto del=[&](int x){
		int cur=col[x];
		cnt[cur]--;
	};
	for(auto v:e[u]){
		if(v==fa||v==son[u])continue;
		for(int i=l[v];i<=r[v];i++)add(id[i]);
	}
	add(u);
	ans[u]=sum;
	if(op==0){
		sum=0;
		for(int i=l[u];i<=r[u];i++)del(id[i]);
	}
}
void solve(){
     cin>>n;
     for(int i=1;i<=n-1;i++){
     	int u,v;cin>>u>>v;
     	e[u].push_back(v);
     	e[v].push_back(u);
     }
     for(int i=1;i<=n;i++)cin>>col[i];
     dfs1(1,0);
     dfs2(1,0,0);
     cin>>m;
     for(int i=1;i<=m;i++){
     	int x;cin>>x;cout<<ans[x]<<endl;
     }
}

Tree and Queries - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

  • 给定一棵 nn 个节点的树，根节点为 11。每个节点上有一个颜色 cic_i。mm 次操作。操作有一种：
    1. u k：询问在以 uu 为根的子树中，出现次数 ≥k\ge k 的颜色有多少种。
  • 2≤n≤1052\le n\le 10^5，1≤m≤1051\le m\le 10^5，1≤ci,k≤1051\le c_i,k\le 10^5。

Sol：还是常规的可以直接dsu on tree.对于add操作，我们先维护颜色的桶，再维护出现次数的桶。删除操作的顺序值得注意，和add需要正好反过来。注意到询问的给出形式，我们需要将询问离线下来，对于同一个节点的U的不同k同时O(1)回答。对于离线问题我们需要保证输出答案的顺序，所以我们需要记录询问编号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
vector<int>e[N];
int sz[N];int son[N];
int cnt[N];int sum[N];
int col[N];
int ans[N];
vector<pii>q[N];
int l[N],r[N],idx=0;int id[N];
void dfs1(int u,int fa){
	sz[u]=1;
	l[u]=++idx;
	id[idx]=u;
	for(auto v:e[u]){
		if(v==fa)continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[v]>sz[son[u]])son[u]=v;
	}
	r[u]=idx;
}

void dfs2(int u,int fa,int op){
	for(auto v:e[u]){
		if(v==fa||v==son[u])continue;
		dfs2(v,u,0);
	}
	if(son[u])dfs2(son[u],u,1);
	auto add=[&](int x){
		int c=col[x];
		cnt[c]++;
		sum[cnt[c]]++;
	};
	auto del=[&](int x){
		int c=col[x];
		sum[cnt[c]]--;
		cnt[c]--;
		
	};
	for(auto v:e[u]){
		if(v==fa||v==son[u])continue;
		for(int i=l[v];i<=r[v];i++){
			add(id[i]);
		}
	}
	add(u);
	for(auto [id,k]:q[u]){
		ans[id]=sum[k];
	}
	if(op==0){
		for(int i=l[u];i<=r[u];i++)del(id[i]);
	}
}
void solve(){
     cin>>n>>m;
     for(int i=1;i<=n;i++)cin>>col[i];
     for(int i=1;i<=n-1;i++){
     	int u,v;cin>>u>>v;
     	e[u].push_back(v);
     	e[v].push_back(u);
     }
     for(int i=1;i<=m;i++){
     	int u,k;cin>>u>>k;
     	q[u].push_back({i,k});
     }
     dfs1(1,0);
     dfs2(1,0,0);
     for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
}

Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：一棵根为 11 的树，每条边上有一个字符（a 到 v 共 2222 种）。一条简单路径被称为 Dokhtar-kosh，当且仅当路径上的字符经过重新排序后可以变成一个回文串。 求每个子树中最长的 Dokhtar-kosh 路径的长度。

说在前面：第一次见到这种判会回文串的套路是在dfs序配树状数组的时候。所谓的套路就是回文串的字母的出现次数最多只能有一个是奇数，其次就是由于我们只需要判断每个元素次数的奇偶性，这可以用异或做到，那再考虑如果出现的字母种类有限，我们可以状态压缩二进制数。

Sol：题解 CF741D 【Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths】 - 洛谷专栏 (luogu.com.cn)

题解 CF741D 【Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths】 - 洛谷专栏 (luogu.com.cn)

提供两篇比较好的代码和思路讲解。我的理解是对于子树问题，如果路径在内部，不经过当前的点，则递归下去去做。如果要求路径经过当前子树的根，则考虑路径两端一定在两颗子树内，进行合并子树过程。对于当前这个模型，要求长度最长，就是两端点距离最长，距离有lca经典公式得到。我们对于么每一个字符集状态维护对应得最大深度，那状态怎么转移保证终态合法。我们考虑只能异或全是偶数次或者一个奇数次得，这等价于异或0或者2的次幂。时间复杂度O(23nlogn)O(23nlogn)

debug：这个获得状态的过程是是从上而下的，需要递归前就得到当前节点的字符状态，懒的调，导致瞪眼一万年.对于叶子节点，答案应该是0，但这样算出来是负的，需要和0取max。调试完的endl没删，导致超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
struct edge{int v,w;};
vector<edge>e[N];
int l[N],r[N],idx=0;int id[N];
int dep[N];int sz[N];int son[N];
int ans[N];int mask[N];int res[M];
void dfs1(int u,int fa){
	sz[u]=1;
	l[u]=++idx;
	id[idx]=u;
	dep[u]=dep[fa]+1;
	for(auto [v,w]:e[u]){
		if(v==fa)continue;
		mask[v]=mask[u]^w;
		dfs1(v,u);
		
		
	//bug(u);bug(mask[u]);	bug(v);bug(mask[v]);
	//	cerr<<endl;
		sz[u]+=sz[v];
		if(sz[v]>sz[son[u]])son[u]=v;
	}
	r[u]=idx;
}

void dfs2(int u,int fa,int op){
	for(auto [v,w]:e[u]){
		if(v==fa||v==son[u])continue;
		dfs2(v,u,0);
	}
	if(son[u])dfs2(son[u],u,1);
	auto add1=[&](int x){
        	ans[u]=max(ans[u],dep[x]+res[mask[x]]);
        	//当只有一个子树的时候不能更新，res初始赋值-inf
        	for(int i=0;i<=21;i++)ans[u]=max(ans[u],dep[x]+res[mask[x]^(1<<i)]);
        };
    auto add2=[&](int x){
    	res[mask[x]]=max(res[mask[x]],dep[x]);
    	//bug(x);bug(mask[x]);bug(dep[x]);bug(res[mask[x]]);
    	//cerr<<endl;
    };
    auto del=[&](int x){
    	res[mask[x]]=-inf;
    };
        for(auto [v,w]:e[u]){
        	if(v==fa||v==son[u])continue;
        	for(int i=l[v];i<=r[v];i++)add1(id[i]);
        	for(int i=l[v];i<=r[v];i++)add2(id[i]);
        }
        add1(u);add2(u);
        ans[u]-=2*dep[u];
        for(auto [v,w]:e[u]){
        	if(v==fa)continue;
        	ans[u]=max(ans[u],ans[v]);
        	}
        if(op==0){
        	for(int i=l[u];i<=r[u];i++)del(id[i]);
        }
        
}
void solve(){
        cin>>n;
        for(int i=2;i<=n;i++){
        	int x;cin>>x;char c;cin>>c;
        	//cerr<<c<<endl;
        	int tmp=(c-'a');
        	//cerr<<tmp<<endl;
        	tmp=(1<<tmp);
        	//cerr<<tmp<<endl;
        	e[i].push_back({x,tmp});
        	e[x].push_back({i,tmp});
        }
        memset(res,-0x3f,sizeof res);
      //  for(int i=0;i<=10;i++)cerr<<res[i]<<" ";
     //   cerr<<endl;
        dfs1(1,0);
        for(int i=1;i<=n;i++){
      //  bug(l[i]);bug(r[i]);bug(sz[i]);
      //  cerr<<endl;
        }
        dfs2(1,0,1);
       // for(int i=1;i<=n;i++)cerr<<ans[i]<<" ";
        for(int i=1;i<=n;i++)cout<<max(ans[i],0)<<" ";
}

to do list:Problem - F - Codeforces

启发式合并,DSU on Tree - nannandbk - 博客园 (cnblogs.com)

Tree Requests - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

2.利用dsu on tree解决树上路径问题

[P4149 IOI2011] Race - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)