DSU on tree
又称 tree 上启发式合并。
适用于统计子树内信息。
原理：贪心。
特征：通常需要一个全局的桶。
实现方法：对于每个节点，先统计「轻子树」并清空桶，再统计「重子树」并保留桶。其中，「重子树」表示每个节点最大的子树，其余则称「轻子树」。
通常需要离线询问。
正确性说明：类似于重链剖分，每个节点的「重子节点」（即「重子树」的根）将会从根到叶子节点形成一条「重链」。正因为是一条链，我们就能每次爬上去时仅需统计当前「重子节点」而无需再次统计整个「重子树」了，但是轻子树就需要再次统计了。
一些性质：
-
一个非叶子节点总是有一个「重儿子」。
-
一个节点可能是其父节点的「重儿子」，却不一定在「重链」上。
-
一个节点至多向上走 \(\log n\) 步就会合并到重链上（考虑树的构建，可以看成是轻子树不断合并到重子树上去，这至少会使树的大小翻倍，而树的大小为 \(n\)，我们最多是从叶子走到根，于是每次翻倍，最多走 \(\log n\) 步，并查集按秩合并也是一样的道理）。
时间复杂度：由性质 \(3\) 可得时间复杂度为 \(O(n \log n)\)（最多 \(n\) 个轻节点，但这显然十分跑不满）。
CF246E
直接上代码爽。
code
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
int heavy;
string name[N];
int siz[N],dep[N],ans[N],son[N];
vector<int> G[N];
struct QUERY{
int id,k;
};
vector<QUERY> qry[N];
set<string> st[N];
void dfs(int cur){ //寻找「重链」
siz[cur]=1;
for(int i:G[cur]){
dep[i]=dep[cur]+1;
dfs(i);
siz[cur]+=siz[i];
if(siz[i]>siz[son[cur]])
son[cur]=i;
}
}
void getans(int cur){ //更新挂在 cur 节点上的询问
for(auto i:qry[cur]){
int pos=dep[cur]+i.k;
if(pos>n+1)
ans[i.id]=0;
else
ans[i.id]=st[pos].size();
}
}
void upd(int cur,int val){ //更新 cur 子树内的信息
if(val==1)
st[dep[cur]].insert(name[cur]);
else
st[dep[cur]].clear();
for(int i:G[cur]){
if(i==heavy) //避开「重子树」，先更新「轻子树」
continue;
upd(i,val);
}
}
void dfs2(int cur,int big){ //按顺序处理子树，其中 big 表示是否为「重子树」
for(int i:G[cur]){
if(i==son[cur]) //避开「重子树」，先处理「轻子树」
continue;
dfs2(i,0);
}
if(son[cur])
dfs2(son[cur],1),heavy=son[cur]; //最后处理 「重子树」
upd(cur,1);
heavy=0; //清空是为了方便将轻子树的重子树一并清空
getans(cur);
if(!big)
upd(cur,-1); //将轻子树信息清空
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
int r;
cin>>name[i]>>r;
G[r].push_back(i);
}
cin>>m;
for(int i=1,v,k;i<=m;i++){
cin>>v>>k;
qry[v].push_back({i,k});
}
dfs(0);
dfs2(0,0);
for(int i=1;i<=m;i++)
cout<<ans[i]<<'\n';
return 0;
}
CF208E
与上题几乎一致，就多加了一个倍增找到 \(p\) 级祖先。
code
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
int heavy;
string name[N];
int siz[N],dep[N],ans[N],son[N],cnt[N],dp[N][31];
vector<int> G[N];
struct QUERY{
int k,id;
};
vector<QUERY> qry[N];
int fnd(int x,int y){
for(int i=21;i>=0;i--)
if(y>=(1<<i))
x=dp[x][i],y-=(1<<i);
return x;
}
void dfs(int cur){
siz[cur]=1;
for(int i:G[cur]){
dfs(i);
siz[cur]+=siz[i];
if(siz[i]>siz[son[cur]])
son[cur]=i;
}
}
void getans(int cur){
for(auto i:qry[cur]){
int pos=dep[cur]+i.k;
if(!cur)
ans[i.id]=0;
else
ans[i.id]=cnt[pos]-1;
}
}
void upd(int cur,int val){
cnt[dep[cur]]+=val;
for(int i:G[cur]){
if(i==heavy)
continue;
upd(i,val);
}
}
void dfs2(int cur,int big){
for(int i:G[cur]){
if(i==son[cur])
continue;
dfs2(i,0);
}
if(son[cur])
dfs2(son[cur],1),heavy=son[cur];
upd(cur,1);
heavy=0;
getans(cur);
if(!big)
upd(cur,-1);
}
void init_lca(int cur,int fa){
dep[cur]=dep[fa]+1;
dp[cur][0]=fa;
for(int i=1;(1<<i)<=dep[cur];i++)
dp[cur][i]=dp[dp[cur][i-1]][i-1];
for(int i:G[cur])
init_lca(i,cur);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
int r; cin>>r;
G[r].push_back(i);
}
cin>>m;
init_lca(0,0);
for(int i=1,v,k;i<=m;i++){
cin>>v>>k;
int pos=fnd(v,k);
qry[pos].push_back({k,i});
}
dfs(0);
dfs2(0,0);
for(int i=1;i<=m;i++)
cout<<ans[i]<<' ';
return 0;
}
CF570D
与上题几乎一致，就多加了一个统计答案时只要出现次数为奇数的字母个数 \(\le 1\) 即为 Yes。
code
//
// CF570D.cpp
//
//
// Created by _XOFqwq on 2024/10/20.
//
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m;
int heavy;
char c[N];
int siz[N],dep[N],son[N];
bool ans[N];
vector<int> G[N];
int cnt[N][31];
struct QUERY{
int id,k;
};
vector<QUERY> qry[N];
void dfs(int cur){
siz[cur]=1;
for(int i:G[cur]){
dep[i]=dep[cur]+1;
dfs(i);
siz[cur]+=siz[i];
if(siz[i]>siz[son[cur]])
son[cur]=i;
}
}
void getans(int cur){
for(auto i:qry[cur]){
int pos=i.k;
if(pos>n)
ans[i.id]=0;
else{
int f=0;
for (char j='a'; j<='z'; j++) {
if (cnt[pos][j]&1) {
f++;
}
}
ans[i.id]=(f<=1);
}
}
}
void upd(int cur,int val){
cnt[dep[cur]][c[cur]]+=val;
for(int i:G[cur]){
if(i==heavy)
continue;
upd(i,val);
}
}
void dfs2(int cur,int big){
for(int i:G[cur]){
if(i==son[cur])
continue;
dfs2(i,0);
}
if(son[cur])
dfs2(son[cur],1),heavy=son[cur];
upd(cur,1);
heavy=0;
getans(cur);
if(!big)
upd(cur,-1);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=2;i<=n;i++){
int r; cin>>r;
G[r].push_back(i);
}
for (int i=1; i<=n; i++) {
cin>>c[i];
}
for(int i=1,v,k;i<=m;i++){
cin>>v>>k;
qry[v].push_back({i,k});
}
dep[1]=1,dfs(1);
dfs2(1,0);
for(int i=1;i<=m;i++)
cout<<(ans[i]?"Yes\n":"No\n");
return 0;
}
所以说 DSU on tree 的题还是很板的（）
标签：Living,cur,int,siz,son,dep,重子,83,Dream From： https://www.cnblogs.com/XOF-0-0/p/18487319