从启发式合并到Dsu on Tree
title: 从启发式合并到Dsu on Tree
categories:
- ICPC
tags:
- null
abbrlink: 2926421d
date: 2023-07-19 00:00:00
从启发式合并到Dsu on Tree
传统启发式合并
[HNOI2009] 梦幻布丁
题目描述
$n$ 个布丁摆成一行，进行 $m$ 次操作。每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。
例如，颜色分别为 $1,2,2,1$ 的四个布丁一共有 $3$ 段颜色.
输入格式
第一行是两个整数，分别表示布丁个数 $n$ 和操作次数 $m$。
第二行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个布丁的颜色 $a_i$。
接下来 $m$ 行，每行描述一次操作。每行首先有一个整数 $op$ 表示操作类型：
- 若 $op = 1$，则后有两个整数 $x, y$，表示将颜色 $x$ 的布丁全部变成颜色 $y$。
- 若 $op = 2$，则表示一次询问。
Sol：考虑初始答案就是看每一个数和自己前面的数是不是一样,算的时候多算n+1的目的是不需要特判处理边界，影响是答案固定需要减1。考虑合并过程，我们希望最后颜色是对的，所以我们保证x是小集合，向y这个大集合合并，但这样只会改变位置，不会改变位置对应的颜色。所以我们需要用modify函数维护位置的颜色，减去原颜色对答案的贡献，增加新颜色对答案的贡献。
//首先考虑统计段数，看与后面的数相同吗，不相同就多一段
//发现答案是和布丁具体颜色无关，只和种类个数有关
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
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.解决子树问题
- 只支持子树查询
- 不支持修改操作
给定一棵树，点带点权，问：最少多少次修改使得树上任意一条简单路径的点权异或和不为0。
Sol：我们只考虑在每条路径的lca处理，这也是树形dp常见的处理出发点。考虑钦定1为根，然后预处理树上异或前缀和d。考虑如果u和v之间存在非法路径，则$d[u]\oplus d[v] \oplus a[lca]$==0 .考虑子树合并的过程中，我们给每个节点维护set，当我们合并子树的时候，我们采用启发式合并，保证合并次数的复杂度是$O(nlogn)$，由于需要用set维护，每次合并的时候复杂度是$O(logn)$,总时间复杂度是$O(nlogn^2)$
考虑具体修改方案，我们只需要修改lca处的点权值改成很大，保证异或的时候高位的1消除不掉即可，所有经过lca的非法路径都将不复存在。
代码使用递归实现，常数较大，且本题使用的是set的启发式合并。后面代码将展示使用dfs序和重儿子优先的方式来减小常数。
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题面：
有一棵 $n$ 个结点的以 $1$ 号结点为根的有根树。
每个结点都有一个颜色，颜色是以编号表示的， $i$ 号结点的颜色编号为 $c_i$。
如果一种颜色在以 $x$ 为根的子树内出现次数最多，称其在以 $x$ 为根的子树中占主导地位。显然，同一子树中可能有多种颜色占主导地位。
你的任务是对于每一个 $i\in[1,n]$，求出以 $i$ 为根的子树中，占主导地位的颜色的编号和。
$n\le 10^5,c_i\le n$
Sol:考虑使用dsu on tree,每次先递归得到轻儿子答案，同时删除影响。再递归重儿子，保留贡献。二次递归轻儿子合并子树计算贡献。为什么不开O(n)个map去存储答案，从空间和时间上来说都非常差，所以我们考虑用一个数组原地修改，维护的答案及时清空。
递归版本：
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肯定快于递归的。
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即可。
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)
- 给定一棵 $n$ 个节点的树，根节点为 $1$。每个节点上有一个颜色 $c_i$。$m$ 次操作。操作有一种：
u k：询问在以 $u$ 为根的子树中，出现次数 $\ge k$ 的颜色有多少种。
- $2\le n\le 10^5$，$1\le m\le 10^5$，$1\le c_i,k\le 10^5$。
Sol：还是常规的可以直接dsu on tree.对于add操作，我们先维护颜色的桶，再维护出现次数的桶。删除操作的顺序值得注意，和add需要正好反过来。注意到询问的给出形式，我们需要将询问离线下来，对于同一个节点的U的不同k同时O(1)回答。对于离线问题我们需要保证输出答案的顺序，所以我们需要记录询问编号。
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)
题意：一棵根为 $1$ 的树，每条边上有一个字符（a 到 v 共 $22$ 种）。一条简单路径被称为 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)$
debug：这个获得状态的过程是是从上而下的，需要递归前就得到当前节点的字符状态，懒的调，导致瞪眼一万年.对于叶子节点，答案应该是0，但这样算出来是负的，需要和0取max。调试完的endl没删，导致超时
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解决树上路径问题
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog！