DSU on Tree and It's questions
树上启发式合并，可以在 \(O(n\log n)\) 的时间复杂度内解决一类对于子树的查询问题。这篇文章以题目为主。
算法流程
- 遍历 \(u\) 的所有轻儿子，计算答案，但不保留其在一个全局的数据结构内的结果。
- 遍历 \(u\) 的重儿子，保留它对一个全局数据结构的影响。
- 遍历 \(u\) 的轻儿子的子树结点，加入这些点对答案的贡献，可以得到 \(u\) 的答案。
复杂度证明
根到树上任意节点的轻边数量不超过 \(\log n\) 条。
证明：我们设根到该节点有 \(x\) 条轻边该子树大小为 \(y\)，显然轻边连接的子节点的子树大小小于父亲的一般，那么 \(y<n/2^x\)，显然 \(n>2^x\)，所以 \(x<\log n\)。
又因为如果一个节点是其父亲的重儿子，任意节点到根的路径上所有重边连接的父节点在计算答案是必定不会遍历到这个节点，所以一个节点的被遍历的次数等于它到根节点路径上的轻边数 \(+1\)。所以一个点的被遍历的次数 \(<\log n+1\)。那么总的时间复杂度就是 \(O(n\log n)\)。
例题
CF208E Blood Cousins
有一个家族关系树，描述了 \(n\ (1\leq n\leq 1e5)\) 人的家庭关系，成员编号为 \(1\) 到 \(n\) 。
如果 \(a\) 是 \(b\) 的父亲，那么称 \(a\) 为 \(b\) 的 \(1\) 级祖先；如果 \(b\) 有一个 \(1\) 级祖先, \(a\) 是 \(b\) 的 \(1\) 级祖先的 \((k-1)\) 级祖先，那么称 \(a\) 为 \(b\) 的 \(k\) 级祖先。
家庭关系保证是一棵树，树中的每个人都只有一个父母，且自己不会是自己的祖先。
如果存在一个人 \(z\) ，是两个人 \(a\) 和 \(b\) 共同的 \(p\) 级祖先：那么称 \(a\) 和 \(b\) 为 \(p\) 级表亲。
\(m\ (1\leq m\leq 1e5)\) 次询问，每次询问给出一对整数 \(v\) 和 \(p\) ，求编号为 \(v\) 的人有多少个 \(p\) 级表亲。
此题可以转化为求 \(v\) 的 \(p\) 级祖先（可使用倍增求）有多少个 \(p\) 级儿子（最后 \(-1\)）。
对询问离线，然后在每个对应的节点上使用一个 vector 挂上对它子树内的询问。
用一个桶记录目前遍历到深度为 \(x\) 的点有多少个，对于每个询问的点 \(u\)，查询其有多少个 \(p\) 级儿子，只需最后求 \(bot_{dep_u+p}\) 即可。时间复杂度 \(O(n\log n)\)。
具体见代码吧
struct Edge{
int enxt[M],head[N],to[M],ent;
inline void addline(int u,int v){
to[++ent]=v;
enxt[ent]=head[u];
head[u]=ent;
}
}e1;
vector<pair<int,int>>que[N];
int n,m,q,root[N];
int dep[N],son[N],fa[N][22],siz[N];
int lef[N],rit[N],tim,lis[N];
int bot[N],ans[N];
void dfs1(int u,int f){
lef[u]=++tim;lis[tim]=u;
dep[u]=dep[fa[u][0]]+1,siz[u]=1;
for(int i=1;i<=18;++i)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=e1.head[u];i;i=e1.enxt[i]){
int v=e1.to[i];
if(v==f)continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
rit[u]=tim;
}
inline int kthfat(int u,int k){
for(int i=0;i<=18;++i)
if((k>>i)&1)u=fa[u][i];
return u;
}
void add(int u,int f){bot[dep[u]]+=f;}
void addit(int u,int f){
for(int i=lef[u];i<=rit[u];++i)
add(lis[i],f);
}
void dfsu(int u){
for(int i=e1.head[u];i;i=e1.enxt[i]){
int v=e1.to[i];
if(v==fa[u][0]||v==son[u])continue;
dfsu(v);addit(v,-1);
}
if(son[u])dfsu(son[u]);
for(int i=e1.head[u];i;i=e1.enxt[i]){
int v=e1.to[i];
if(v==fa[u][0]||v==son[u])continue;
addit(v,1);
}
add(u,1);
for(int i=0;i<(int)que[u].size();++i)
ans[que[u][i].second]=bot[dep[u]+que[u][i].first]-1;
}
int main(){
n=read();
for(int i=1;i<=n;++i){
int x=read();
if(!x)root[++m]=i;
else e1.addline(x,i),fa[i][0]=x;
}
for(int i=1;i<=m;++i)
dfs1(root[i],0);
q=read();
for(int i=1;i<=q;++i){
int x=read(),k=read();
if(dep[x]<=k)continue;
int u=kthfat(x,k);
que[u].push_back({k,i});
}
for(int i=1;i<=m;++i){
dfsu(root[i]);
addit(root[i],-1);//记得清空
}
for(int i=1;i<=q;++i)
printf("%d ",ans[i]);
putchar('\n');
return 0;
}
CF246E Blood Cousins Return
给定一片森林，森林中每个节点有一个字符串作为名字。对于询问 \(u,k\)，求出节点 \(u\) 的 \(k\) 级儿子中有多少个不同的名字。
首先用一个 map 对名字离散化。
使用一个 set 来记录子树中的点的编号，顺便去重。
然后就没了。（dsu 板子是这样的）
然后实现加入和删除的时候可以使用 dfs 序减小常数，这个也不是很难。
const int N=500005,M=1000006,INF=0x3f3f3f3f;
set<int>se[N];
vector<pair<int,int>>que[N];
int n,q,val[N],fat[N],ans[N];
map<string,int>lis;int tot;
int siz[N],son[N],dep[N];
int lef[N],rit[N],tim,idx[N];
void dfs1(int u){
lef[u]=++tim;idx[tim]=u;
dep[u]=dep[fat[u]]+1;siz[u]=1;
for(int i=e1.head[u];i;i=e1.enxt[i]){
int v=e1.to[i];
dfs1(v);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
rit[u]=tim;
}
inline void add(int u){se[dep[u]].insert(val[u]);}
inline void addit(int u){
for(int i=lef[u];i<=rit[u];++i)
add(idx[i]);
}
inline void delit(int u){
for(int i=lef[u];i<=rit[u];++i)
se[dep[idx[i]]].clear();
}
void dfsu(int u){
for(int i=e1.head[u];i;i=e1.enxt[i]){
int v=e1.to[i];
if(v==son[u])continue;
dfsu(v);delit(v);
}
if(son[u])dfsu(son[u]);
for(int i=e1.head[u];i;i=e1.enxt[i]){
int v=e1.to[i];
if(v==son[u])continue;
addit(v);
}add(u);
for(int i=0;i<(int)que[u].size();++i)
ans[que[u][i].second]=se[que[u][i].first+dep[u]].size();
}
int main(){
ios::sync_with_stdio(0);cin>>n;
for(int i=1;i<=n;++i){
int x;string s;
cin>>s>>x;
if(lis.find(s)==lis.end())lis[s]=++tot;
val[i]=lis[s];
fat[i]=x;
if(x)e1.addline(x,i);
}
for(int i=1;i<=n;++i)
if(!fat[i])dfs1(i);
cin>>q;
for(int i=1;i<=q;++i){
int x,k;cin>>x>>k;
que[x].push_back({k,i});
}
for(int i=1;i<=n;++i)
if(!fat[i]){dfsu(i);delit(i);
for(int i=1;i<=q;++i)
printf("%d\n",ans[i]);
putchar('\n');
return 0;
}
CF600E Lomsat gelral
有一棵 \(n\) 个结点的以 \(1\) 号结点为根的有根树。
每个结点都有一个颜色，颜色是以编号表示的， \(i\) 号结点的颜色编号为 \(c_i\)。
如果一种颜色在以 \(x\) 为根的子树内出现次数最多，称其在以 \(x\) 为根的子树中占主导地位。显然，同一子树中可能有多种颜色占主导地位。
你的任务是对于每一个 \(i\in[1,n]\)，求出以 \(i\) 为根的子树中，占主导地位的颜色的编号和。
\(n\le 10^5,c_i\le n\)
线段树合并板子题
其实也是 dsu on tree 的板子题。具体做法就是开一个桶记录每个颜色的点的编号和（当然是现在遍历到的），然后这个标号和的最大值显然可以在加入的过程中动态地维护。然后就没了。
这题我是用线段树合并做的。就不贴代码了。
CF375D Tree and Queries
- 给定一棵 \(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\)。
也是很板子的一道题了。
用一个桶记录目前遍历到的点的颜色的数量。动态统计出现次数大于 \(k\) 的颜色数。
然后就没了啊。代码占版面，就不贴了。link
CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
一棵根为 1 的树，每条边上有一个字符（a-v共22种）。 一条简单路径被称为Dokhtar-kosh当且仅当路径上的字符经过重新排序后可以变成一个回文串。 求每个子树中最长的Dokhtar-kosh路径的长度。
一道有一定技巧的 dsu 题目。
显然状态压缩，对每个小写字母，对应到二进制数的一位。
对于回文串，这意味着至多只有一个字符出现过奇数次，其他字符都出现偶数次。
因此，dsu 时，对于每个点 \(u\)，就是求过点 \(u\) 的路径的异或值是否能表示为 \(0\) 或 \(2^x\)。
那么就像点分治一样，将目前遍历的子树内到当前根的异或值存入桶中，然后用新加入的子树的节点到根的异或值分别与 \(0\) 和 \(2^x\) 异或后的值在桶里查询。
具体见代码吧。
int n,ans[N],bot[(1<<22)+1];
int siz[N],son[N],fat[N],dep[N],dis[N];
int stk[N],top;
void dfs1(int u,int f){
siz[u]=1,dep[u]=dep[f]+1,fat[u]=f;
for(int i=e1.head[u];i;i=e1.enxt[i]){
int v=e1.to[i],w=e1.weight[i];
if(v==f)continue;
dis[v]=dis[u]^w;
dfs1(v,u);//别和上一行写反了
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
void getlis(int u){
stk[++top]=u;
for(int i=e1.head[u];i;i=e1.enxt[i]){
int v=e1.to[i];
if(v==fat[u])continue;
getlis(v);
}
}
void addit(int u){
bot[dis[u]]=max(bot[dis[u]],dep[u]);
for(int i=e1.head[u];i;i=e1.enxt[i]){
int v=e1.to[i];
if(v==fat[u])continue;
addit(v);
}
}
void delit(int u){
bot[dis[u]]=0;
for(int i=e1.head[u];i;i=e1.enxt[i]){
int v=e1.to[i];
if(v==fat[u])continue;
delit(v);
}
}
void dfs(int u){
for(int i=e1.head[u];i;i=e1.enxt[i]){//1
int v=e1.to[i];
if(v==fat[u]||v==son[u])continue;
dfs(v);ans[u]=max(ans[u],ans[v]);
delit(v);
}
if(son[u]){//2
dfs(son[u]);
ans[u]=max(ans[u],ans[son[u]]);
}
for(int k=0;k<22;++k)//统计答案
if(bot[dis[u]^(1<<k)])
ans[u]=max(ans[u],bot[dis[u]^(1<<k)]-dep[u]);
if(bot[dis[u]])ans[u]=max(ans[u],bot[dis[u]]-dep[u]);
bot[dis[u]]=max(bot[dis[u]],dep[u]);//更新桶内信息
for(int i=e1.head[u];i;i=e1.enxt[i]){//3
int v=e1.to[i];
if(v==fat[u]||v==son[u])continue;
top=0;getlis(v);
for(int i=1;i<=top;++i){
for(int k=0;k<22;++k)
if(bot[dis[stk[i]]^(1<<k)])
ans[u]=max(ans[u],bot[dis[stk[i]]^(1<<k)]+dep[stk[i]]-2*dep[u]);
if(bot[dis[stk[i]]])ans[u]=max(ans[u],bot[dis[stk[i]]]+dep[stk[i]]-2*dep[u]);
}
addit(v);
}
}
int main(){
n=read();char s[2];
for(int i=2;i<=n;++i){
int u=read();scanf("%s",s);
e1.addedge(u,i,1<<(s[0]-'a'));
}
dfs1(1,0);
dfs(1);
for(int i=1;i<=n;++i)
printf("%d ",ans[i]);
putchar('\n');
return 0;
}
CF570D Tree Requests
给定一个以 \(1\) 为根的 \(n\) 个结点的树，每个点上有一个字母（
a-z），每个点的深度定义为该节点到 \(1\) 号结点路径上的点数。每次询问 \(a, b\) 查询以 \(a\) 为根的子树内深度为 \(b\) 的结点上的字母重新排列之后是否能构成回文串。
相信有上面这些题的铺垫，这题解决起来也并不会很难。
开一个 \(26\times n\) 的桶，记录目前遍历到的深度为 \(i\) 的点中字母为 \(c\) 的有多少个。
对于每个查询操作，就只需查桶中的为奇数的数是否小于等于 \(1\) 即可。代码
CF715C Digit Tree
给定一棵树，边权 \(1 \leq w\leq 9\)。给定一个数 \(M\)，保证 \(\gcd(M,10)=1\)。
对于一对有序的不同的顶点 \((u, v)\)，他沿着从顶点 \(u\) 到顶点 \(v\) 的最短路径，按经过顺序写下他在路径上遇到的所有数字（从左往右写），如果得到一个可以被 \(M\) 整除的十进制整数，那么就认为 \((u,v)\) 是有趣的点对。
求有趣的对的数量。
难点不在 dsu，而在于推式子。
预处理 \(up_u\) 表示 \(u\) 到根节点的路径的值，\(down_u\) 表示根节点到 \(u\) 的路径的值。这两个信息可以预处理得到。若 \(v\in son_u,edge_{u,v}=w\)，则：
\[up_v=10^{dep_u}\times w+up_u\\ down_v=10\times down_u+w \]根据 dsu 的套路，统计一条路径 \(u\to v\) 的答案，还需统计 \(lca\) 的信息。
\(u\to lca\) 的答案：\(\frac{up_u-up_{lca}}{10^{dep_{lca}}}\)。
\(lca\to v\) 的答案：\(down_v-down_{lca}\times10^{dep_v-dep_{lca}}\)
所以总的答案：
\[\frac{up_u-up_{lca}}{10^{dep_{lca}}}\times 10^{dep_v-dep_{lca}}+down_v-down_{lca}\times10^{dep_v-dep_{lca}}\equiv0\mod{m} \]发现在 dsu 的过程中，如果 \(u\) 点先加入待查询的数据结构中，而 \(v\) 点统计 \(u\) 的答案，则只能统计 \(u\to v\) 的答案，而不能统计 \(v\to u\) 的答案。这启发我们加入 \(u\) 点的时候向两个不同的数据结构中分别加入其作为起始点或终点时需要记录的信息。
作为起始点时，可以将式子变形为：
\[up_u\equiv down_{lca}\times 10^{dep_{lca}}-\frac{down_v\times 10^{2\times dep_{lca}}}{10^{dep_v}}+ up_{lca}\mod{m} \]作为重点时候，\(down_v\) 和 \(dep_v\) 均要在式子中体现，根据上面一个式子，我们可以变形出：
\[\frac{down_v}{dep_v}\equiv \frac{down_{lca}}{10^{dep_{lca}}}-\frac{{up_u-up_{lca}}}{10^{2\times dep_{lca}}}\mod{m} \]具体实现的时候用两个 map 分别记录 \(up_u\) 和 \(\frac{down_v}{dep_v}\) 的这些值对应的出现过的次数即可。
然后注意点是 \(m\) 不一定是质数，但是保证了\(\gcd(m,10)=1\)，所以可以使用拓展欧几里得求解这些形如 \(10^x\) 的数的逆元。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar();}
while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
const int N=300005;
int n,siz[N],son[N],dep[N];ll m,upv[N],dwn[N],pwr[N],ans;
typedef pair<int,ll>ttfa;
vector<ttfa>edge[N];
map<ll,ll>um,dm;
ll exgcd(ll a,ll b,ll&x,ll&y){
//printf("exgcd %lld %lld %lld %lld\n",a,b,x,y);
if(b==0){x=1,y=0;return a;}
ll gcd=exgcd(b,a%b,x,y),tmp=x;
x=y,y=tmp-a/b*y;
return gcd;
}
inline ll inv(ll a){
//printf("inv %lld\n",a);
ll x,y;exgcd(a,m,x,y);
return (x%m+m)%m;
}
void dfsp(int u,int f){
siz[u]=1;
for(auto ttf:edge[u]){
int v=ttf.first;ll w=ttf.second;
if(v==f)continue;
dep[v]=dep[u]+1;
upv[v]=(upv[u]+pwr[dep[u]]*w%m)%m;
dwn[v]=(dwn[u]*10ll%m+w)%m;
dfsp(v,u);
siz[u]+=siz[v];
if(siz[v]>=siz[son[u]])son[u]=v;
}
}
inline void add(int u){um[upv[u]]++,dm[dwn[u]*inv(pwr[dep[u]])%m]++;}
inline void calc(int u,int lca){
ll x=(dwn[lca]*pwr[dep[lca]]%m-dwn[u]*pwr[2*dep[lca]]%m*inv(pwr[dep[u]])%m+upv[lca]+m)%m;
ans+=um[x];
x=(dwn[lca]*inv(pwr[dep[lca]])%m-(upv[u]-upv[lca]+m)%m*inv(pwr[2*dep[lca]])%m+m)%m;
ans+=dm[x];
}
void getans(int u,int f,int lca){
calc(u,lca);
for(auto ttf:edge[u]){
int v=ttf.first;
if(v==f)continue;
getans(v,u,lca);
}
}
void addit(int u,int f){
add(u);
for(auto ttf:edge[u]){
int v=ttf.first;
if(v==f)continue;
addit(v,u);
}
}
void dfsu(int u,int f){
for(auto ttf:edge[u]){
int v=ttf.first;
if(v==f||v==son[u])continue;
dfsu(v,u);um.clear(),dm.clear();
}
if(son[u])dfsu(son[u],u);
for(auto ttf:edge[u]){
int v=ttf.first;
if(v==f||v==son[u])continue;
getans(v,u,u);addit(v,u);
}
calc(u,u);add(u);
}
int main(){
n=read(),m=read();
pwr[0]=1;
for(int i=1;i<=2*n;++i)pwr[i]=pwr[i-1]*10ll%m;
for(int i=1;i<n;++i){
int u=read()+1,v=read()+1;ll w=read();
edge[u].push_back({v,w});
edge[v].push_back({u,w});
}
dep[1]=1;dfsp(1,0);
dfsu(1,0);
printf("%lld\n",ans);
return 0;
}
后记
dsu on tree 的题目主要以 CF 上的为主。CF 上也有一著名的关于 dsu 的博客。
more and more vegetable