Living-Dream 系列笔记第83期

0-0 / 2024-10-29 / 原文

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 的题还是很板的（）