当前位置：首页 > news >正文

树上启发式合并系列题解

news 2025/5/7 3:31:34

树上启发式合并

树上启发式合并（dsu on tree）是一种巧妙的暴力。用一个全局数组存储结果，对于每棵子树，有以下操作：

先遍历轻儿子，处理完轻儿子后将数组清零（遍历一次来清零）；
遍历重儿子（ $big_u$ ，下同），遍历完不用清零，再遍历，将轻儿子合并到重儿子上去，其合并结果存储于全局数组；
用此时的全局数组来计算父亲。

让高度小的树成为高度较大的树的子树，这个优化就是启发式合并算法。

根据重链划分的思想，如同树剖那般，时间复杂度是 $\Theta(n\log_2n)$ 的，具体证明见OI - WIKI。

在树上处理 $u$ 子树内的信息（各种子树内的数组、答案变量等），修改永久/不永久贡献，可以直接遍历子树 $u$ （跳过 $big_u$ ），也可以用 dfs 序遍历子树（我习惯用前者）。

前文说，重儿子的贡献保留，其余的要清空，那么给一个 $k ee p$ 标记看是否保留：如果是重儿子就 $k ee p = 1$ ，否则 $k ee p = 0$ 且要记得删贡献。

那么我们发现，如果 $k ee p = 0$ ，那么这一子树内的贡献都将会弃用，对比莫队的 $\textrm {add}$ 和 $\textrm {del}$ 函数，在删除贡献时不需要刻意维护答案所对应的变量，这在接下来对于编码的正确性讨论有重要作用。

ll siz[N],big[N];
void dfs1(ll u,ll fa)
{siz[u]=1;for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa)continue;dfs1(v,u);if(!big[u]||siz[big[u]]<siz[v])big[u]=v;//重儿子}
}
ll ans[N];
void add(ll u,ll fa,ll Big)
{//增for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa||v==Big)continue;add(v,u,Big);}
}
void del(ll u,ll fa)
{//删for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa)continue;del(v,u);}
}
void dfs2(ll u,ll fa,bool keep)//keep:是否保存贡献
{for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa||v==big[u])continue;dfs2(v,u,0);}if(big[u])dfs2(big[u],u,1);add(u,fa,big[u]);ans[u]=//获取答案if(!keep)del(u,fa);
}

对比树上莫队根据 dfs 序，把每棵子树拍平的 $\Theta(n\sqrt{n})$ ，显然树上启发式合并的 $\Theta(n\log_2n)$ 更具有优势！（在这里也算是把树上莫队的坑填上了）

来看到例题：我的题单。

1.CF600E Lomsat gelral

题意

在这里插入图片描述
$1\le c\le 10^5$ ， $1\le c_i\le n$ 。

思路

题目询问每个子树内节点最多出现的颜色，并且要求颜色编号相加。我们不妨在树上做出每个子树内的答案，考虑使用树上启发式合并。

求众数当然使用桶了。我们对于每棵子树维护一个桶 $c n t$ ， $ma$ 为颜色出现的最多次数， $sco l$ 为出现次数为 $ma$ 的颜色编号的总和（即答案）。其实三者都是很容易维护的：

cnt[c[u]]++;
if(cnt[c[u]]>ma)
{ma=cnt[c[u]];scol=c[u];//重新计算
}
else if(cnt[c[u]]==ma)scol+=c[u];

其实初学者（包括我），可能对删除贡献时对答案的维护有些纠结——到底要不要维护正确的 $ma$ 和 $sco l$ 呢？

其实是不需要的，因为在这一子树 $v$ 下的 $ma$ 和 $c n t$ ，在其他子树维护自己子树内的信息时并非必需；哪怕是之后祖先 $u$ 的子树，也不会因为不遍历子树 $v$ 而节省多少时间，相反更为麻烦。

因此删除贡献的时候，清空桶（不能 memset），然后（全局的） $ma$ 和 $sco l$ 重置为 $0$ 即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e5+9;
ll n,c[N];
ll idx,head[N];
struct edge
{ll to,next;
}e[N<<1];
void addedge(ll u,ll v)
{idx++;e[idx].to=v;e[idx].next=head[u];head[u]=idx;
}
ll ti,dfn[N],L[N],R[N],siz[N],big[N];
ll cnt[N],ma,ans[N],scol;
void dfs1(ll u,ll fa)
{L[u]=++ti;siz[u]=1;dfn[ti]=u;for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa)continue;dfs1(v,u);siz[u]+=siz[v];if(!big[u]||siz[big[u]]<siz[v])big[u]=v;}R[u]=ti;
}
void add(ll u,ll fa,ll Big)
{cnt[c[u]]++;if(cnt[c[u]]>ma){ma=cnt[c[u]];scol=c[u];}else if(cnt[c[u]]==ma)scol+=c[u];for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa||v==Big)continue;add(v,u,Big);}
}
void del(ll u,ll fa)
{cnt[c[u]]--;for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa)continue;del(v,u);}
}
void dfs2(ll u,ll fa,bool keep)
{for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa||v==big[u])continue;dfs2(v,u,0);}if(big[u])dfs2(big[u],u,1);add(u,fa,big[u]);ans[u]=scol;if(!keep)del(u,fa),ma=scol=0;
}
int main()
{scanf("%lld",&n);for(int i=1;i<=n;i++)scanf("%lld",&c[i]);for(int i=1;i<n;i++){ll u,v;scanf("%lld%lld",&u,&v);addedge(u,v);addedge(v,u);}dfs1(1,0);dfs2(1,0,0);for(int i=1;i<=n;i++)printf("%lld ",ans[i]);return 0;
}

2.CF570D Tree Requests

题意

给定一个以 $1$ 为根的 $n$ 个结点的树，每个点上有一个字母，均为 $26$ 个小写字母的其中一个。每个点的深度定义为该节点到 $1$ 号结点路径上的点数。

给出 $m$ 次询问，每次询问 $u, d$ 查询以 $u$ 为根的子树内深度为 $d$ 的结点上的字母重新排列之后是否能构成回文串。可以则输出 yes，否则输出 no。

如果 $u$ 为根的子树内不存在深度为 $d$ 的节点，也算存在回文串。

$1\le n,m\le 5\times 10^5$ 。

思路

显然的，如果一堆字母重新排序之后，可以组成回文串，仅当每个字母出现个数 $cnt_{a\sim z}$ 中，奇数的个数不大于 $1$ 。

对于子树 $u$ ，维护每个深度上的字母桶即可。将询问离线在树上处理就好了，用个 vector 存每个询问 $u_i$ 的所有询问深度就好了。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5e5+9;
ll n,m;
char c[N];
ll idx,head[N];
struct edge
{ll to,next;
}e[N<<1];
void addedge(ll u,ll v)
{idx++;e[idx].to=v;e[idx].next=head[u];head[u]=idx;
}
struct que
{ll d,id;
};
vector<que>q[N];
ll siz[N],big[N],dep[N];
ll cnt[N][28],ans[N];
void dfs1(ll u,ll fa)
{dep[u]=dep[fa]+1;siz[u]=1;for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa)continue;dfs1(v,u);siz[u]+=siz[v];if(!big[u]||siz[big[u]]<siz[v])big[u]=v;}
}
void add(ll u,ll fa,ll Big)
{ll col=c[u]-'a'+1;cnt[dep[u]][col]++;for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa||v==Big)continue;add(v,u,Big);}
}
void del(ll u,ll fa)
{ll col=c[u]-'a'+1;cnt[dep[u]][col]--;for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa)continue;del(v,u);}
}
void dfs2(ll u,ll fa,bool keep)
{for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa||v==big[u])continue;dfs2(v,u,0);}if(big[u])dfs2(big[u],u,1);add(u,fa,big[u]);for(auto t:q[u]){ll odd=0;for(int i=1;i<=26;i++)odd+=(cnt[t.d][i]&1);ans[t.id]=(odd<=1);}if(!keep)del(u,fa);
}
int main()
{scanf("%lld%lld",&n,&m);for(int i=2;i<=n;i++){ll u;scanf("%lld",&u);addedge(u,i);addedge(i,u);}for(int i=1;i<=n;i++)cin>>c[i];for(int i=1;i<=m;i++){ll u,d;scanf("%lld%lld",&u,&d);q[u].push_back((que){d,i});}dfs1(1,0);dfs2(1,0,0);for(int i=1;i<=m;i++){if(ans[i])puts("Yes");else puts("No");}return 0;
}

3.CF1009F Dominant Indices

题意

在这里插入图片描述
$1\le n\le 10^6$ 。

思路

对于 $u$ 子树内的节点，对于每个深度维护一个节点个数桶 $cnt_{dep}$ ，找出出现次数最大的 $cnt_{dep}$ 及其对应的最小的 $D = d e p$ ，答案就是 $D-dep_u$ 。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e6+9;
ll n;
ll idx,head[N];
struct edge
{ll to,next;
}e[N<<1];
void addedge(ll u,ll v)
{idx++;e[idx].to=v;e[idx].next=head[u];head[u]=idx;
}
ll big[N],siz[N],dep[N];
void dfs1(ll u,ll fa)
{siz[u]=1;dep[u]=dep[fa]+1;for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa)continue;dfs1(v,u);siz[u]+=siz[v];if(!big[u]||siz[big[u]]<siz[v])big[u]=v;}
}
ll cnt[N],ma,Dep,ans[N];
void add(ll u,ll fa,ll Big)
{cnt[dep[u]]++;if(cnt[dep[u]]>ma){ma=cnt[dep[u]];Dep=dep[u];}else if(cnt[dep[u]]==ma){Dep=min(Dep,dep[u]);}for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa||v==Big)continue;add(v,u,Big);}
}
void del(ll u,ll fa)
{cnt[dep[u]]--;for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa)continue;del(v,u);}
}
void dfs2(ll u,ll fa,bool keep)
{for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa||v==big[u])continue;dfs2(v,u,0);}if(big[u])dfs2(big[u],u,1);add(u,fa,big[u]);ans[u]=Dep-dep[u];if(!keep)del(u,fa),ma=Dep=0;
}
int main()
{scanf("%lld",&n);for(int i=1;i<n;i++){ll u,v;scanf("%lld%lld",&u,&v);addedge(u,v);addedge(v,u);}dfs1(1,0);dfs2(1,0,0);for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);return 0;
}

4.CF375D Tree and Queries

题意

在这里插入图片描述

思路

这其实是训练树上莫队的题目，不过也可以用树上启发式合并来做，二者思路其实相同，都是整 $\textrm{add}$ 和 $\textrm{del}$ 。

我们还是维护一个桶，不过这题有个 trick 就是维护“桶中桶”： $ccnt_k$ 表示颜色个数大于等于 $k$ 的数量。

不过不知为何，树上启发式合并在 SMOJ 可以通过，但是在 Codeforces 会被卡常，因此在这里贴上两种代码：

代码 1：树上启发式合并 TLE on #53 in Codeforces

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read()
{ll s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
inline void write(ll x)
{ if(x==0){putchar('0');return;}ll len=0,k1=x,c[10005];if(k1<0)k1=-k1,putchar('-');while(k1)c[len++]=k1%10+'0',k1/=10;while(len--)putchar(c[len]);
}
const ll N=1e5+9;
ll n,m,c[N];
ll idx,head[N];
struct edge
{ll to,next;
}e[N<<1];
void addedge(ll u,ll v)
{idx++;e[idx].to=v;e[idx].next=head[u];head[u]=idx;
}
struct que
{ll k,id;
};
vector<que>q[N];
ll siz[N],big[N];
void dfs1(ll u,ll fa)
{siz[u]=1;for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa)continue;dfs1(v,u);if(!big[u]||siz[big[u]]<siz[v])big[u]=v;}
}
ll cnt[N],ccnt[N],ans[N];
void add(ll u,ll fa,ll Big)
{cnt[c[u]]++;ccnt[cnt[c[u]]]++;for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa||v==Big)continue;add(v,u,Big);}
}
void del(ll u,ll fa)
{ccnt[cnt[c[u]]]--;cnt[c[u]]--;for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa)continue;del(v,u);}
}
void dfs2(ll u,ll fa,bool keep)
{for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa||v==big[u])continue;dfs2(v,u,0);}if(big[u])dfs2(big[u],u,1);add(u,fa,big[u]);for(auto t:q[u])ans[t.id]=ccnt[t.k];if(!keep)del(u,fa);
}
int main()
{n=read(),m=read();for(int i=1;i<=n;i++)c[i]=read();for(int i=1;i<n;i++){ll u,v;u=read(),v=read();addedge(u,v);addedge(v,u);}for(int i=1;i<=m;i++){ll u,k;u=read(),k=read();q[u].push_back((que){k,i});}dfs1(1,0);dfs2(1,0,0);for(int i=1;i<=m;i++)write(ans[i]),puts("");return 0;
}

代码 2：树上莫队 AC

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read()
{ll s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
inline void write(ll x)
{ if(x==0){putchar('0');return;}ll len=0,k1=x,c[10005];if(k1<0)k1=-k1,putchar('-');while(k1)c[len++]=k1%10+'0',k1/=10;while(len--)putchar(c[len]);
}
const ll N=1e6+9;
ll n,m,a[N],l,r;
ll bitSize,res,b[N],cnt[N],sum[N],ans[N];
struct query
{ll l,r,v,k,id;
}q[N];
bool cmp(query x,query y)
{if(b[x.l]!=b[y.l])return b[x.l]<b[y.l];if(b[x.l]&1)return x.r<y.r;return x.r>y.r;
}
ll u,v,k;
ll idx,head[N<<1];
struct edge
{ll to,next; 
}e[N<<1];
void addedge(ll u,ll v)
{idx++;e[idx].to=v;e[idx].next=head[u];head[u]=idx;
}
ll dfn[N<<1],ti,st[N<<1],en[N<<1];
void dfs(ll u,ll fa)
{dfn[++ti]=u;st[u]=ti;for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa)continue;dfs(v,u);}en[u]=ti;
}
void add(ll x)
{cnt[a[x]]++;sum[cnt[a[x]]]++;
}
void del(ll x)
{sum[cnt[a[x]]]--;cnt[a[x]]--;
}
int main()
{n=read(),m=read();bitSize=sqrt(n);for(int i=1;i<=n;i++){a[i]=read();b[i]=(i-1)/bitSize+1;}for(int i=1;i<n;i++){u=read(),v=read();addedge(u,v);addedge(v,u);}dfs(1,0);for(int i=1;i<=m;i++){u=read(),k=read();q[i]=(query){st[u],en[u],u,k,i};}sort(q+1,q+m+1,cmp);ll l=1,r=0;for(int i=1;i<=m;i++){[添加链接描述](https://blog.csdn.net/m0_60506105/article/details/147345312?spm=1001.2014.3001.5501)while(r<q[i].r)add(dfn[++r]);while(r>q[i].r)del(dfn[r--]);while(l<q[i].l)del(dfn[l++]);while(l>q[i].l)add(dfn[--l]);ans[q[i].id]=sum[q[i].k];}for(int i=1;i<=m;i++)write(ans[i]),printf(" ");return 0;
}