首页 > 其他分享 >树上启发式合并

树上启发式合并

时间：2023-01-04 22:35:33浏览次数：57  
标签：cnt int sum 合并 son MAXN 启发式 树上 id

树上启发式合并

\(\text{By DaiRuiChen007}\)

一、算法简介

在解决树上问题时，我们经常遇到需要统计多个节点各自的子树信息的情况，对于一般暴力统计的 \(\Theta(n^2)\) 复杂度，对于解决题目往往是不够的，这时，我们可以考虑采用 DSU on Tree 即树上启发式合并（或称静态链分治）的算法将其优化到 \(\Theta(\log n)\) 的复杂度

DSU on Tree 相对于平凡的暴力的优化在于：DSU on Tree 在每次递归时，会保留其重儿子的答案并且加到当前节点的贡献中

实现 DSU on Tree 一般分为四步执行：

  1. 递归解决该节点轻儿子的问题，不保留当前答案
  2. 递归解决该节点重儿子的问题，保留当前答案
  3. 统计该节点所有轻儿子的子树的贡献，得出最终答案
  4. 如果当前答案不需要保留，清空该子树的答案

DSU on Tree 的核心在于函数：add 和 del，他们的作用分别是统计或删除某一个节点的贡献，在这点上 DSU on Tree 和莫队较为相似

关于 DSU on Tree 的时间复杂度：由于每个儿子被考虑的次数等同于这个节点到根上的轻边数量，显然，这个复杂度是 \(\Theta(\log n)\) 的，所以其总体复杂度为 \(\Theta(n\log n)\)

关于对树上路径的统计，除了点分治算法之外，DSU on Tree 也不失为一种强力的算法，我们可以将树上路径 \(u\to v\) 拆成 \(u\to\operatorname{LCA}(u,v)\) 和 \(\operatorname{LCA}(u,v)\to v\)，每次统计答案的时候将当前节点作为 \(\operatorname{LCA}(u,v)\)，对于每一个子节点 \(u\)，查询在 \(u\) 以外的子树中的 \(v\) 的个数，注意由于我们需要保证树上路径为简单路径，所以我们选择的路径 \((u,v)\) 不能在当前节点的同一棵子树内，要先统计这棵子树做为 \(u\) 时的答案，然后再将这棵子树里的所有节点作为可能的 \(v\) 计算贡献

二、典例分析

I. [CodeForces375D] - Tree and Queries

\(\text{Link}\)

思路分析

用 \(cnt_i\) 维护当前颜色 \(i\) 出现的次数，用 \(sum_x\) 维护出现次数 \(\ge x\) 的颜色个数，那么我们可以在每次加减 \(cnt\) 的同时加减 \(sum\)，得到如下的贡献统计函数

时间复杂度 \(\Theta(n\log n)\)

inline void add(int color) {
	++cnt[color];
	++sum[cnt[color]];
}
inline void del(int color) {
	--sum[cnt[color]];
	--cnt[color];
}

代码呈现

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+1;
int n,m;
int col[MAXN],cnt[MAXN],sum[MAXN],ans[MAXN];
vector <int> edge[MAXN];
struct node {
	int k,id;
};
vector <node> query[MAXN];
inline void add(int color) {
	++cnt[color];
	++sum[cnt[color]];
}
inline void del(int color) {
	--sum[cnt[color]];
	--cnt[color];
}
int fa[MAXN],siz[MAXN],son[MAXN],id[MAXN],rnk[MAXN],idcnt;
inline void dfs(int p,int f) {
	fa[p]=f,siz[p]=1;
	id[p]=++idcnt,rnk[idcnt]=p;
	for(int v:edge[p]) {
		if(v==f) continue;
		dfs(v,p);
		siz[p]+=siz[v];
		if(siz[v]>siz[son[p]]) son[p]=v;
	}
}
inline void dsu(int p,bool rsv) {
	for(int v:edge[p]) {
		if(v==fa[p]||v==son[p]) continue;
		dsu(v,false);
	}
	if(son[p]) dsu(son[p],true);
	add(col[p]);
	for(int v:edge[p]) {
		if(v==fa[p]||v==son[p]) continue;
		for(int x=id[v];x<id[v]+siz[v];++x) add(col[rnk[x]]);
	}
	for(auto t:query[p]) ans[t.id]=sum[t.k];
	if(!rsv) for(int x=id[p];x<id[p]+siz[p];++x) del(col[rnk[x]]);
}
signed main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&col[i]);
	for(int i=1;i<n;++i) {
		int u,v;
		scanf("%d%d",&u,&v);
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	for(int i=1;i<=m;++i) {
		int u,k;
		scanf("%d%d",&u,&k);
		query[u].push_back((node){k,i});
	}
	dfs(1,0);
	dsu(1,true);
	for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
	return 0;
}

拓展解法

记录每个节点的 dfn 序，查询点 \(p\) 的答案时候等价于在区间 \([dfn_p,dfn_p+siz_p-1]\) 上做查询，也可以使用莫队解决，时间复杂度 \(\Theta(n\sqrt n)\)

另解代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+1;
int n,m,block;
int col[MAXN],cnt[MAXN],sum[MAXN],ans[MAXN];
int siz[MAXN],id[MAXN],rnk[MAXN],idcnt;
vector <int> edge[MAXN];
struct node {
	int l,r,k,id;
	inline friend bool operator <(const node &x,const node &y) {
		if(x.l/block==y.l/block) return x.r<y.r;
		else return x.l<y.l;
	}
} q[MAXN];
inline void add(int pos) {
	int color=col[rnk[pos]];
	++cnt[color];
	++sum[cnt[color]];
}
inline void del(int pos) {
	int color=col[rnk[pos]];
	--sum[cnt[color]];
	--cnt[color];
}
inline void dfs(int p,int f) {
	siz[p]=1,id[p]=++idcnt,rnk[idcnt]=p;
	for(int v:edge[p]) {
		if(v==f) continue;
		dfs(v,p);
		siz[p]+=siz[v];
	}
}
signed main() {
	scanf("%d%d",&n,&m);
	block=pow(n,0.455);
	for(int i=1;i<=n;++i) scanf("%d",&col[i]);
	for(int i=1;i<n;++i) {
		int u,v;
		scanf("%d%d",&u,&v);
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	dfs(1,0);
	for(int i=1;i<=m;++i) {
		int u,k;
		scanf("%d%d",&u,&k);
		q[i]=(node){id[u],id[u]+siz[u]-1,k,i};
	}
	sort(q+1,q+m+1);
	int l=1,r=0;
	for(int i=1;i<=m;++i) {
		while(l<q[i].l) del(l++);
		while(l>q[i].l) add(--l);
		while(r>q[i].r) del(r--);
		while(r<q[i].r) add(++r);
		l=q[i].l,r=q[i].r,ans[q[i].id]=sum[q[i].k];
	}
	for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
	return 0;
}

II. [CodeForces600E] Most gelral

\(\text{Link}\)

思路分析

类似上一题，用 \(sum_x\) 维护其出现次数 \(\ge x\) 的颜色的编号和，用 \(lst\) 维护出现次数最多的颜色的出现次数，每次插入删除的时候顺便更新一下 \(lst\) 即可（更像莫队了。。。），得到如下贡献统计：

inline void add(int clr) {
	++cnt[clr]; 
	if(!sum[cnt[clr]]) lst=cnt[clr];
	sum[cnt[clr]]+=clr;
}
inline void del(int clr) {
	sum[cnt[clr]]-=clr;
	if(!sum[cnt[clr]]) lst=cnt[clr]-1;
	--cnt[clr];

时间复杂度 \(\Theta(n\log n)\)

代码呈现

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+1;
int n;
int col[MAXN],cnt[MAXN],sum[MAXN],ans[MAXN],lst=0;
vector <int> edge[MAXN];
struct node {
	int k,id;
};
vector <node> query[MAXN];
inline void add(int clr) {
	++cnt[clr]; 
	if(!sum[cnt[clr]]) lst=cnt[clr];
	sum[cnt[clr]]+=clr;
}
inline void del(int clr) {
	sum[cnt[clr]]-=clr;
	if(!sum[cnt[clr]]) lst=cnt[clr]-1;
	--cnt[clr];
}
int fa[MAXN],siz[MAXN],son[MAXN],id[MAXN],rnk[MAXN],idcnt;
inline void dfs(int p,int f) {
	fa[p]=f,siz[p]=1;
	id[p]=++idcnt,rnk[idcnt]=p;
	for(int v:edge[p]) {
		if(v==f) continue;
		dfs(v,p);
		siz[p]+=siz[v];
		if(siz[v]>siz[son[p]]) son[p]=v;
	}
}
inline void dsu(int p,bool rsv) {
	for(int v:edge[p]) {
		if(v==fa[p]||v==son[p]) continue;
		dsu(v,false);
	}
	if(son[p]) dsu(son[p],true);
	add(col[p]);
	for(int v:edge[p]) {
		if(v==fa[p]||v==son[p]) continue;
		for(int x=id[v];x<id[v]+siz[v];++x) add(col[rnk[x]]);
	}
	ans[p]=sum[lst];
	if(!rsv) for(int x=id[p];x<id[p]+siz[p];++x) del(col[rnk[x]]);
}
signed main() {
	scanf("%lld",&n);
	for(int i=1;i<=n;++i) scanf("%lld",&col[i]);
	for(int i=1;i<n;++i) {
		int u,v;
		scanf("%lld%lld",&u,&v);
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	dfs(1,0);
	dsu(1,true);
	for(int i=1;i<=n;++i) printf("%lld ",ans[i]);
	puts("");
	return 0;
}

III. [CodeForces246E] Blood Cousins Return

\(\text{Link}\)

思路分析

对于到根节点的每个深度维护一个桶记录当前子树对应深度的名字，由于要满足不可重，所以这里直接采用 set 维护，插入删除等价于在 set 中执行 insert 或 delete 操作，注意查询答案是在深度为 \(dep_{u}+k\) 的桶里查询，为了防止访问的时候出现数组越界，建议把桶的下标开到两倍

注意原题是森林，不妨把 \(0\) 直接当成根节点

时间复杂度 \(\Theta(n\log^2 n)\)

代码呈现

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+1;
int n,m,ans[MAXN],root;
int dep[MAXN],fa[MAXN],siz[MAXN],son[MAXN],id[MAXN],rnk[MAXN],idcnt;
string str[MAXN];
set <string> ver[MAXN<<1];
vector <int> edge[MAXN];
struct node {
	int k,id;
};
vector <node> query[MAXN];
inline void add(int id) {
	ver[dep[id]].insert(str[id]);
}
inline void del(int id) {
	ver[dep[id]].erase(str[id]);
}
inline void dfs(int p,int f) {
	fa[p]=f,siz[p]=1,dep[p]=dep[f]+1;
	id[p]=++idcnt,rnk[idcnt]=p;
	for(int v:edge[p]) {
		if(v==f) continue;
		dfs(v,p);
		siz[p]+=siz[v];
		if(siz[v]>siz[son[p]]) son[p]=v;
	}
}
inline void dsu(int p,bool rsv) {
	for(int v:edge[p]) {
		if(v==fa[p]||v==son[p]) continue;
		dsu(v,false);
	}
	if(son[p]) dsu(son[p],true);
	add(p);
	for(int v:edge[p]) {
		if(v==fa[p]||v==son[p]) continue;
		for(int x=id[v];x<id[v]+siz[v];++x) add(rnk[x]);
	}
	for(auto t:query[p]) ans[t.id]=ver[dep[p]+t.k].size();
	if(!rsv) for(int x=id[p];x<id[p]+siz[p];++x) del(rnk[x]);
}
signed main() {
	cin>>n; 
	for(int i=1;i<=n;++i) {
		int f;
		cin>>str[i]>>f;
		edge[f].push_back(i);
		edge[i].push_back(f);
	}
	cin>>m;
	for(int i=1;i<=m;++i) {
		int u,k;
		cin>>u>>k;
		query[u].push_back((node){k,i});
	}
	dfs(0,0);
	dsu(0,true);
	for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
	return 0;
}

IV. [Codeforces570D] Tree Requests

\(\text{Link}\)

思路分析

对于每个深度 \(d\) 统计当前子树中深度为 \(d\) 的节点里字母 a 到 z 分别出现多少次，想要让他们重排后得到一个回文串，其充分必要条件是出现次数为奇数的字符数量 \(\le 1\)，和上一题类似，查答案的时候暴力即可，也可以维护对应的奇数出现次数，时间复杂度 \(\Theta(n\log n)\)

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+1;
int n,m;
int cnt[MAXN][26],siz[MAXN],son[MAXN],id[MAXN],rnk[MAXN],fa[MAXN],dep[MAXN],idcnt;
bool ans[MAXN];
char ch[MAXN];
struct node {
	int k,id;
};
vector <int> edge[MAXN];
vector <node> query[MAXN];
inline void add(int pos) {
	++cnt[dep[pos]][ch[pos]-'a'];
}
inline void del(int pos) {
	--cnt[dep[pos]][ch[pos]-'a'];
}
inline bool check(int dpth) {
	bool use=false;
	for(int i=0;i<26;++i) {
		if(cnt[dpth][i]&1) {
			if(use) return false;
			else use=true;
		}
	}
	return true;
}
inline void dfs(int p,int f) {
	siz[p]=1,fa[p]=f,dep[p]=dep[f]+1;
	id[p]=++idcnt,rnk[idcnt]=p;
	for(int v:edge[p]) {
		if(v==f) continue;
		dfs(v,p);
		siz[p]+=siz[v];
		if(siz[v]>siz[son[p]]) son[p]=v;
	}
}
inline void dsu(int p,bool rsv) {
	for(int v:edge[p]) {
		if(v==fa[p]||v==son[p]) continue;
		dsu(v,false);
	}
	if(son[p]) dsu(son[p],true);
	add(p);
	for(int v:edge[p]) {
		if(v==fa[p]||v==son[p]) continue;
		for(int x=id[v];x<id[v]+siz[v];++x) add(rnk[x]);
	}
	for(node t:query[p]) ans[t.id]=check(t.k);
	if(!rsv) for(int x=id[p];x<id[p]+siz[p];++x) del(rnk[x]); 
	return ;
}
signed main() {
	scanf("%d%d",&n,&m);
	for(int i=2;i<=n;++i) {
		int f;
		scanf("%d",&f);
		edge[f].push_back(i);
		edge[i].push_back(f);
	}
	scanf("%s",ch+1);
	for(int i=1;i<=m;++i) {
		int u,k;
		scanf("%d%d",&u,&k);
		query[u].push_back((node){k,i});
	}
	dfs(1,0);
	dsu(1,true);
	for(int i=1;i<=m;++i) {
		if(ans[i]) puts("Yes");
		else puts("No");
	}
	return 0;
}

V. [计蒜客A1082] - 青云的机房组网方案

\(\text{Link}\)

思路分析

数论+树论=？

设 \(m=\max\limits_{i=1}^{n}\{a_i\}\le10^5\)，\(p_1,p_2\sim,p_k\) 为 \(1\sim m\) 中的所有质数

设 \(\mathbf P_{x}\) 表示所有满足 \(x|a_i\) 的点两两之间构成的路径集合，\(d(\mathbf P_x)\) 表示 \(\mathbf P_x\) 中所有路径的长度之和，则有：

\[\begin{aligned} \text{Answer} &=d(\mathbf P_1)-d(\mathbf P_{p_1}\cup\mathbf P_{p_2}\cup\cdots\cup\mathbf P_{p_m})\\ &=d(\mathbf P_1)-\sum d(\mathbf P_{p_i})+\sum d(\mathbf P_{p_i}\cap\mathbf P_{p_j})-\sum d(\mathbf P_{p_i}\cap \mathbf P_{p_j}\cap\mathbf P_{p_j})+\cdots\\ &=d(\mathbf P_1)-\sum d(\mathbf P_{p_i})+\sum d(\mathbf P_{p_i\times p_j})-\sum d(\mathbf P_{p_i\times p_j\times p_k})+\cdots\\ \end{aligned} \]

对于 \(1\sim m\) 中的每个数 \(x\)，考虑 \(d(\mathbf P_x)\) 对答案的贡献 \(\lambda(x)\)，其中 \(\lambda(x)\) 是一个特殊的数论函数

则又有：

\[\text{Answer}=\sum_{x=1}^m \lambda(x)\times d(\mathbf P_x) \]

比较一下上下两式的系数可得：

  • 若 \(x=1\)，则 \(\lambda(x)=1\)
  • 若 \(x\) 中含有两个相同的质因子，则 \(\lambda(x)=0\)
  • 若 \(x\) 中仅含有 \(k\) 个互不相同的质因子，则 \(\lambda(x)=(-1)^k\)

通过比对，可以发现 \(\lambda(x)=\mu(x)\)

因此原式化为：

\[\text{Answer}=\sum_{x=1}^m \mu(x)\times d(\mathbf P_x) \]

所以对于某条路径 \(u\to v\)，设 \(p=\operatorname{LCA}(u,v)\)，其对答案的贡献应该为：

\[\sum_{x|a_u,x|a_v} \mu(x)\times(dep_{u}+dep_v-2\times dep_p) \]

对于类似树上路径统计的问题，我们优先考虑 DSU on Tree，枚举 \(\operatorname{LCA}(u,v)\) 和 \(u\)，则对于所有 \(v\) 的贡献之和应该为：

\[\sum_{x|a_u} \mu(x)\sum_{x|a_v}dep_u+dep_v-2\times dep_p \]

考虑把 \(dep_u-2\times dep_p\) 的贡献提取出来，我们开两个桶分别维护：

\[\begin{aligned} cnt_{x,0}&=\sum\limits_{v} [x|a_v]\\ cnt_{x,1}&=\sum\limits_{v} [x|a_v]\times dep_v \end{aligned} \]

统计所有 \(v\) 的贡献之和可以转为：

\[\sum_{x|a_u} \mu(x)\times\left[cnt_{x,0}\times(dep_u-2\times dep_p)+cnt_{x,1}\right] \]

所以我们只需要在每次插入/删除/统计节点的时候枚举 \(a_u\) 的每个子节点的贡献即可

设 \(d(x)\) 表示 \(x\) 的因子个数，则时间复杂度 \(\Theta(\log n\times \sum d(a_i))\)

代码呈现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+1;
int mu[MAXN],a[MAXN],n;
int id[MAXN],rnk[MAXN],siz[MAXN],fa[MAXN],dep[MAXN],son[MAXN],idcnt;
int cnt[MAXN][2],ans;
bool isc[MAXN];
vector <int> edge[MAXN],factor[MAXN];
inline void init() {
	for(int i=1;i<MAXN;++i) mu[i]=1;
	for(int i=2;i<MAXN;++i) {
		if(isc[i]) continue;
		for(int j=i;j<MAXN;j+=i) {
			isc[j]=true;
			if(j%(i*i)!=0) mu[j]*=-1;
			else mu[j]=0;
		}
	}
	for(int i=1;i<MAXN;++i) {
		for(int j=i;j<MAXN;j+=i) {
			factor[j].push_back(i);
		}
	}
}
inline void dfs(int p,int f) {
	id[p]=++idcnt,rnk[idcnt]=p;
	siz[p]=1,fa[p]=f,dep[p]=dep[f]+1;
	for(int v:edge[p]) {
		if(v==f) continue;
		dfs(v,p);
		siz[p]+=siz[v];
		if(siz[v]>siz[son[p]]) son[p]=v;
	}
}
inline void modify(int u,int op) {
	for(int x:factor[a[u]]) {
		cnt[x][0]+=op;
		cnt[x][1]+=op*dep[u];
	}
}
inline void calc(int u,int lca) {
	for(int x:factor[a[u]]) {
		ans+=mu[x]*(cnt[x][0]*(dep[u]-dep[lca]*2)+cnt[x][1]);
	}
}
inline void dsu(int p) {
	for(int v:edge[p]) {
		if(v==fa[p]||v==son[p]) continue;
		dsu(v);
		for(int x=id[v];x<id[v]+siz[v];++x) modify(rnk[x],-1);
	}
	if(son[p]) dsu(son[p]);
	for(int v:edge[p]) {
		if(v==fa[p]||v==son[p]) continue;
		for(int x=id[v];x<id[v]+siz[v];++x) calc(rnk[x],p);
		for(int x=id[v];x<id[v]+siz[v];++x) modify(rnk[x],1);
	}
	calc(p,p);
	modify(p,1);
}
signed main() {
	init();
	scanf("%lld",&n);
	for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
	for(int i=1;i<n;++i) {
		int u,v;
		scanf("%lld%lld",&u,&v);
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	dfs(1,0);
	dsu(1);
	printf("%lld\n",ans);
	return 0;
}

标签：cnt,int,sum,合并,son,MAXN,启发式,树上,id
From： https://www.cnblogs.com/DaiRuiChen007/p/17026174.html

相关文章

  • 合并加密的m3u8
    0x01工具ffmpeg.exe如果没有则使用以下地址下载0x02m3u8格式我的m3u8内容是：#EXTM3U#EXT-X-VERSION:3#EXT-X-TARGETDURATION:6#EXT-X-PLAYLIST-TYPE:VOD#EXT-X-M......
  • 习题2.5 两个有序链表序列的合并 (15 分)
    本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。函数接口定义：ListMerge(ListL1,ListL2);其中List结构定义如下：typedefstructNode......
  • git部分合并代码
    比如在分支A上修改了两次，第一次修改了B文件，第二次修改了C文件，提交之后，我们查看一下log发现最近有两次的提交日志：一个是b文件的提交，一个是c文件的提交，然后都有对应的提交i......
  • git合并分支时禁止合并特定文件
    开发过程中经常会遇到这样的场景，一个项目可能有develop(开发环境)、release(生产环境)等多个分支，经常需要对分支进行合并，但是不同分支下的一些配置文件可能会有所不同，比如......
  • Java 合并PDF文件
    这篇文章主要介绍如何在Java应用程序中实现将多个PDF文件合并为一个PDF的功能。使用组件：Spire.PDFforJava使用以下代码前，需要下载​​Spire.PDFforJava​​包并解压，然后......
  • 剑指25. 合并两个有序链表
    问题描述https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/description/解题思路参考这个代码#Definitionforsingly-linkedlist.#cla......
  • C++实现线性表-顺序表的合并操作代码
    #include<iostream>#include<cstdlib>//C++动态分配存储空间usingnamespacestd;#defineOK1#defineERROR0#defineMAXSIZE100typedefintElemtype;typedefintStat......
  • 双指针+位运算+离散化+区间合并
    双指针+位运算+离散化+区间合并双指针算法可以是两个指针分别指向两个序列，也可以是两个指针指向一个序列，维护一段区间核心思想：将\(O(n^2)\)优化到\(O(n)\)本质上就......
  • git使用添加分支，合并分支，回滚
    git添加分支然后push新的分支切换到添加的分支上修改代码不影响master上的代码修改代码如下，添加一行注释commit到本地如果出现错误可以本地回滚然后push到远程仓......
  • 【命令行copy命令】将php与jpg图片合并
    合成jpgD:\file\合成>copy/bhan1.jpg+bad.phphan4.jpg合成ExcelD:\file\合成>copy/bSys_Dept_合成.xls+bad.phpDept1.xls copy命令 ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99