首页 > 其他分享 >【学习笔记】(19) 启发式合并

【学习笔记】(19) 启发式合并

时间:2023-08-15 16:33:30浏览次数:42  
标签:Head ch fa 19 笔记 son int 启发式 dis

启发式合并

启发式合并核心思想就一句话:把小集合的合并到大的里。

启发式合并思想可以放到很多数据结构里,链表、线段树、甚至平衡树都可以。

考虑时间复杂度,设总共有 \(n\) 个元素,由于每次集合的大小至少翻倍,所以至多会合并 \(logn\) 次,总的复杂度就是 \(O(nlogn)\) 的(结合线段树合并就是 \(O(nlog^2n)\) 的)

dsu on tree 就是树上启发式合并。

dsu on tree 优雅的思想

对于以 u 为根的子树

①. 先统计它轻子树(轻儿子为根的子树)的答案,统计完后删除信息

②. 再统计它重子树(重儿子为根的子树)的答案 ,统计完后保留信息

③. 然后再将重子树的信息合并到 u上

④. 再去遍历 u 的轻子树,然后把轻子树的信息合并到 u 上

⑤. 判断 u 的信息是否需要传递给它的父节点(u 是否是它父节点的重儿子)

dsu on tree 暴力的操作体现于统计答案上(不同的题目统计方式不一样)

例题

Ⅰ.CF570D Tree Requests

重排之后能否构成回文串,即判断出现次数为奇数的字符个数是否小于等于1

因为要多次询问以某个点为根深度为 \(b\) 的节点上的字母

所以可以对每个节点开个 vector,再把和它有关的询问保存在vector

然后在 dsu on tree 的过程进行到该节点时遍历这个节点的 vector (相关询问)

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
const int N = 1e6 + 67;
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int n, m, tot;
int Head[N], to[N], Next[N];
int a[N], son[N], sz[N], d[N];
vector<pair<int, int> > Q[N];
bool vis[N];
int b[N][26], ct[N], ans[N];
void add(int u, int v){
	to[++tot] = v, Next[tot] = Head[u], Head[u] = tot;
}
void dfs1(int x, int fa){
	d[x] = d[fa] + 1, sz[x] = 1;
	for(int i = Head[x]; i; i = Next[i]){
		int y = to[i]; if(y == fa) continue;
		dfs1(y, x), sz[x] += sz[y];
		if(sz[y] > sz[son[x]]) son[x] = y;
	}
}
void calc(int x, int fa){
	if(b[d[x]][a[x]]) ct[d[x]]--;
	else ct[d[x]]++;
	b[d[x]][a[x]] ^= 1;
	for(int i = Head[x]; i; i = Next[i]){
		int y = to[i]; if(y == fa || vis[y]) continue;
		calc(y, x);
	}
}
void dfs2(int x, int fa, int opt){
	for(int i = Head[x]; i; i = Next[i]){
		int y = to[i]; if(y == fa || y == son[x]) continue;
		dfs2(y, x, 0);
	}
	if(son[x]) dfs2(son[x], x, 1), vis[son[x]] = 1;
	calc(x, fa), vis[son[x]] = 0;
	for(auto it : Q[x])
		ans[it.second] = (ct[it.first] <= 1);
	if(!opt) calc(x, fa);
}
int main(){
	n = read(), m = read();
	for(int i = 2; i <= n; ++i){
		int u = read();
		add(u, i), add(i, u);
	}
	for(int i = 1; i <= n; ++i) {
		char ch; cin >> ch;
		a[i] = ch - 'a';
	}
	for(int i = 1; i <= m; ++i){
		int u = read(), k = read();
		Q[u].pb(mp(k, i));
	}
	dfs1(1, 0), dfs2(1, 0, 0);
	for(int i = 1; i <= m; ++i) 
		printf("%s\n", ans[i] ? "Yes" : "No");
	return 0;
} 

Ⅱ.CF375D Tree and Queries

开个数组 \(cnt_i\) 表示 \(i\) 种颜色有多少个,\(f_i\) 表示数量大于 \(i\) 的有多少种。

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 67;
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int n, m, tot;
int fa[N], sz[N], son[N];
int c[N], cnt[N], ans[N], f[N];
int Head[N], to[N], Next[N]; 
vector<pii> Q[N];
bool vis[N];
void add(int u, int v){
	to[++tot] = v, Next[tot] = Head[u], Head[u] = tot;
}
void dfs1(int x, int f){
	fa[x] = f, sz[x] = 1;
	for(int i = Head[x]; i; i = Next[i]){
		int y = to[i]; if(y == fa[x]) continue;
		dfs1(y, x); sz[x] += sz[y];
		if(sz[y] > sz[son[x]]) son[x] = y;
	}
}
void calc(int x, int val){
	if(val == 1) f[cnt[c[x]] += val]++;
	else --f[cnt[c[x]]], cnt[c[x]] += val;
	for(int i = Head[x]; i; i = Next[i]){
		int y = to[i]; if(y == fa[x] || vis[y]) continue;
		calc(y, val);
	}
}
void dfs2(int x, int opt){
	for(int i = Head[x]; i; i = Next[i]){
		int y = to[i]; if(y == fa[x] || y == son[x]) continue;
		dfs2(y, 0);
	}
	if(son[x]) dfs2(son[x], 1), vis[son[x]] = 1;
	calc(x, 1), vis[son[x]] = 0;
	for(auto it : Q[x])
		ans[it.second] = f[it.first];
	if(!opt) calc(x, -1);
}
int main(){
	n = read(), m = read();
	for(int i = 1; i <= n; ++i) c[i] = read();
	for(int i = 1; i < n; ++i){
		int u = read(), v = read();
		add(u, v), add(v, u);
	}
	for(int i = 1; i <= m; ++i){
		int u = read(), k = read();
		Q[u].pb(mp(k, i));
	}
	dfs1(1, 0), dfs2(1, 0);
	for(int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
	return 0;
} 

Ⅲ. P4149 [IOI2011] Race

树上两点 \(u,v\) 的距离为 \(dis_u + dis_v - 2 \times dis_{lca(u,v)}\),边的数量为 \(d_u + d_v - 2 \times d_{lca(u,v}\) 。

那么问题就转换成在树上找到两点 \(u,v\) 使得 \(dis_u+dis_v−2×dis_{lca(u,v)}=k\) 且 \(d_u+d_v−2×d_{lca(u,v)}\) 尽可能小。

于是我们可以定义 \(minn_d\) 表示当前距离 \(1\) 号点距离为 \(d\) 的节点的最小深度。

因为我们计算两点的简单路径权值和、两点简单路径的边的个数是根据它们的lca ,所以一个分支内的节点不能相互影响

所以需要先对一个分支统计完贡献后,再添加它的信息

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define int long long
using namespace std;
const int N = 5e5 + 67;
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int n, m, k, tot, ans = 0x3f3f3f3f3f3f3f3f;
int fa[N], sz[N], son[N], d[N], dis[N];
int Head[N], to[N], Next[N], edge[N]; 
map<int, int> minn;
void add(int u, int v, int w){
	to[++tot] = v, Next[tot] = Head[u], Head[u] = tot, edge[tot] = w;
}
void dfs1(int x, int f){
	fa[x] = f, sz[x] = 1, d[x] = d[f] + 1;
	for(int i = Head[x]; i; i = Next[i]){
		int y = to[i]; if(y == fa[x]) continue;
		dis[y] = dis[x] + edge[i], dfs1(y, x), sz[x] += sz[y];
		if(sz[y] > sz[son[x]]) son[x] = y;
	}
}
void calc(int x, int rt){
	int s = k + 2 * dis[rt] - dis[x];
	if(minn.count(s)) ans = min(ans, minn[s] + d[x] - d[rt] * 2);
	for(int i = Head[x]; i; i = Next[i]){
		int y = to[i]; if(y == fa[x]) continue;
		calc(y, rt);
	}
}
void change(int x){
	if(minn.count(dis[x])) minn[dis[x]] = min(minn[dis[x]], d[x]);
	else minn[dis[x]] = d[x];
	for(int i = Head[x]; i; i = Next[i]){
		int y = to[i]; if(y == fa[x]) continue;
		change(y);
 	}
}
void dfs2(int x, int opt){
	for(int i = Head[x]; i; i = Next[i]){
		int y = to[i]; if(y == fa[x] || y == son[x]) continue;
		dfs2(y, 0);
	}
	if(son[x]) dfs2(son[x], 1);
	int s = k + dis[x];
	if(minn.count(s)) ans = min(ans, minn[s] - d[x]);minn[dis[x]] = d[x];
	for(int i = Head[x]; i; i = Next[i]){
		int y = to[i]; if(y == fa[x] || y == son[x]) continue;
		calc(y, x), change(y);
	}
	if(!opt) minn.clear();
}
signed main(){
	n = read(), k = read();
	for(int i = 1; i < n; ++ i){
		int u = read() + 1, v = read() + 1, w = read();
		add(u, v, w), add(v, u, w);
	}
	dfs1(1, 0), dfs2(1, 0); 
	printf("%lld\n", ans == 0x3f3f3f3f3f3f3f3f ? -1 : ans);
	return 0;
} 

Ⅳ.CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

Ⅴ. P5290 [十二省联考 2019] 春节十二响

参考:https://www.cnblogs.com/GsjzTle/p/14033777.html

标签:Head,ch,fa,19,笔记,son,int,启发式,dis
From: https://www.cnblogs.com/jiangchen4122/p/17455915.html

相关文章

  • ARCHICAD 26(建筑设计软件) v26.4019英文版
    ARCHICAD26是一款领先的建筑设计软件,为建筑师、设计师和工程师提供了全面的工具和功能,用于创建、分析和可视化复杂的建筑项目。点击获取ARCHICAD26 ARCHICAD26建立在先前版本的成功基础上,为用户提供了更强大、更高效的建筑设计工具。首先,ARCHICAD26引入了新的Param-O......
  • 关于2023年8月19日PMP认证考试准考信下载通知
    各位考生:为保证参加2023年8月19日PMI项目管理资格认证考试的每位考生都能顺利进入考场参加考试,请完整阅读本通知内容。一、关于准考信下载为确保您顺利进入考场参加8月份考试,请及时登录本网站(https://event.chinapmp.cn/)个人系统下载并打印准考信,准考信下载时间为2023年8月15日-8......
  • Java学习笔记(十)
    第7章 面向对象(下)7.1 静态的1、static:静态的2、什么是静态的?和对象无关的,不会因为对象的不同而不同,即所有对象都一样的。换句话说,和对象无关。动态的,根据对象的不同而不同,和对象有关,由对象动态决定。3、static这个关键字用在哪里?(1)成员变量前面:静态变量(2)成员方法前面:静态......
  • 传热和传质基本原理-学习笔记
    传热的三种方式:传导:  不同物质形态的传导机理:  气体:气体分子的能量与其随机的平移有关,也和内部旋转和震动运动有关。可以把基于分子的随机运动的净能量传输说成是的能量扩散。       液体:与气体情况几乎相同,但流体分子靠得更近,分子间的相互作用更强,也更频繁。  ......
  • 8.15集训笔记
    上午测试讲题U259234累加累乘/accmul分析:直接开两个变量记录答案即可,使用for循环n次,对于s1也可以使用等差数列求和公式。点击查看代码#include<bits/stdc++.h>usingnamespacestd;intn;intmain(){cin>>n;ints1=0,s2=1;for(inti=1;i<=n;i++){......
  • 【刷题笔记】22. Generate Parentheses
    题目Given n pairsofparentheses,writeafunctiontogenerateallcombinationsofwell-formedparentheses.Forexample,given n =3,asolutionsetis:["((()))","(()())","(())()","()(())","()()(......
  • Programming abstractions in C阅读笔记p111-p113: boilerplate
    《ProgrammingAbstractionsInC》学习第47天,p111-p113,总结如下:一、技术总结1.boilerplate/**File:random.h*Version:1.0*LastmodifiedonFriJul2216:44:361994byeroberts*-----------------------------------------------------*Thisinterfacepr......
  • Programming abstractions in C阅读笔记p111-p113: boilerplate
    《ProgrammingAbstractionsInC》学习第47天,p111-p113,总结如下:一、技术总结1.boilerplate/**File:random.h*Version:1.0*LastmodifiedonFriJul2216:44:361994byeroberts*-----------------------------------------------------*Thisinterfaceprovi......
  • Ceph RBD的使用笔记
    ceph的内容太多了,单独写一篇文章记录自己的一些RBD的学习笔记,其实简书和其他博客上已经记录的非常全面了,但是因为出处都比较分散,所以还是自己把自己的实验记录一下便于以后学习的查阅。也感谢各位大佬的无私分享。 1.RBD池的创建和enable[cephadmin@ceph-node~]$cephosdp......
  • [二分图] 学习笔记
    定义无向图可以分成两个点集,集合内的点不相连通,不允许存在奇环//二分图的判定#include<bits/stdc++.h>usingnamespacestd;constintN=1e3+10,M=2e6+10;struct{ intto,next;}e[M];inttop,h[N],color[N],n,m;voidadd(intx,inty){ e[++top]......