Dsu On Tree 筆記

關(guān)于這個(gè)技巧我甚至都記不清是什么時(shí)候?qū)W的了，反正就是很早很早之前，當(dāng)時(shí)學(xué)了之后看什么子樹查詢都想上 Dsu On Tree，后來(lái)也沒怎么寫過(guò)了，不過(guò)這個(gè)東西確確實(shí)實(shí)很強(qiáng)勁。

今天寫了一上午教練的題單，大概獲得了三天的時(shí)間來(lái)寫自己想寫的，就去寫寫各種莫隊(duì)吧。

結(jié)果寫到一個(gè)樹上莫隊(duì)，突然想使用這個(gè)東西，于是想著順便寫一些這個(gè)東西的文章。

由于忘了 CF 賬號(hào)，所以好多寫過(guò)的題都忘了是啥了，所以接下來(lái)是入門向的，目的防止我自己忘掉。

引入

對(duì)于一些樹上的問(wèn)題，每次查詢子樹，并且這些信息難以合并，需要開個(gè)桶或者使用 DS 進(jìn)行維護(hù)，我們可以嘗試這個(gè)東西。

如果 \(O(1)\) 一次查詢或刪改，這個(gè)東西的復(fù)雜度是 \(O(nlogn)\) 的。

這個(gè)東西在一定程度上可以替代點(diǎn)分治，注意我指的是一定程度上。

我們的整個(gè)算法是有一個(gè)特定的流程的，所以寫起來(lái)是異常的簡(jiǎn)單。

就按照 OIWIKI 上的例子來(lái)引入吧。

給你一棵數(shù)，有一些詢問(wèn)，問(wèn)你一個(gè)子樹中的顏色數(shù)量是多少。

很好理解的題意。

我們發(fā)現(xiàn)判斷顏色的數(shù)量，必須一定程度上去維護(hù)每一個(gè)顏色的信息，顯然這個(gè)東西難以進(jìn)行有效的合并，所以容易想到開桶維護(hù)每一個(gè)顏色的出現(xiàn)個(gè)數(shù)，暴力掃描每一個(gè)子樹，明顯這個(gè)算法是 \(O(n^2)\) 級(jí)別的。

這個(gè)桶就是數(shù)組維護(hù)每個(gè)顏色的出現(xiàn)次數(shù)，怕我的語(yǔ)言過(guò)分抽象。

先不談我們?cè)趺礈p少這類做法的時(shí)間復(fù)雜度，我們先思考有什么辦法來(lái)減輕我們的工作量。

我們可以嘗試這么一個(gè)方案：假設(shè)我們?cè)谔幚硪豢米訕涞臅r(shí)候，我們肯定是要 dfs 到下邊的子樹的，所以我們可以在桶里邊保留一些東西的貢獻(xiàn)，這個(gè)樣子我們似乎就可以稍微優(yōu)化一些了。

我們來(lái)討論一下如何進(jìn)行合法的保留，仔細(xì)思索后我們會(huì)發(fā)現(xiàn)能保留的東西是很苛刻的。

我們是無(wú)法保留兩個(gè)子樹的，所以貪心來(lái)想，我們?nèi)ミx擇重兒子所在的子樹進(jìn)行保留就行。

這個(gè)重兒子就是我們樹鏈剖分的那個(gè)重兒子，別告訴我有人連樹剖都不會(huì)。

這樣我們就成功進(jìn)行了優(yōu)化，現(xiàn)在這個(gè)東西大概就是 \(O(nlogn)\) 級(jí)別的了。

什么？這就完了？憑什么？我不信。

我們冷靜分析一波，來(lái)思考一下每個(gè)節(jié)點(diǎn)會(huì)被掃到多少次？

容易發(fā)現(xiàn)，在某個(gè)節(jié)點(diǎn)到根中路徑中，我們除去它本身會(huì)被遍歷的這一次，這個(gè)路徑中每出現(xiàn)一次輕邊，這個(gè)點(diǎn)就會(huì)被掃一次，又因?yàn)檫@個(gè)數(shù)目不會(huì)超過(guò) \(log n\) 級(jí)別的，所以 \(O(nlogn)\) 的時(shí)間復(fù)雜度也并不難理解了。

引入的解答

我們來(lái)考慮一下如何解決上邊的引入。

給一下鏈接：https://www.luogu.com.cn/problem/U41492

按照上邊的思路，我們寫一下最經(jīng)典的樹剖，讀入，這個(gè)我們不多說(shuō)了，結(jié)下來(lái)我們講一下 dsu on tree 的基本流程。

不保留對(duì)桶中的貢獻(xiàn)，嘗試去解決輕兒子所在子樹
保留對(duì)桶中的貢獻(xiàn)，解決重兒子所在子樹
再一次遍歷輕兒子所在子樹，把這一次的東西加入桶中，計(jì)算答案。

int siz[MN], son[MN], dfn_cnt, l[MN], r[MN], col[MN], tmp[MN];
void dfs1(int u, int father){
	siz[u]=1; l[u]=++dfn_cnt; col[dfn_cnt]=tmp[u];
	for(int i=head[u];i;i=node[i].nxt){
		int v=node[i].to;
		if(v==father) continue;
		dfs1(v,u); siz[u]+=siz[v];
		if(siz[son[u]]<siz[v]) son[u]=v;
	}
	r[u]=dfn_cnt;
}
int cnt[MN], res, ans[MN];
vector <int> querys[MN];
void Add(int col){
	cnt[col]++;
	if(cnt[col]==1) res++;
}
void Del(int col){
	cnt[col]--;
	if(cnt[col]==0) res--;
}
int Getans(){
	return res;
}
void solve(int u, int father, bool keep){
	for(int i=head[u];i;i=node[i].nxt){
		int v=node[i].to;
		if(v==father||v==son[u]) continue;
		solve(v,u,false);
	}
	if(son[u]) solve(son[u],u,true);
	for(int i=head[u];i;i=node[i].nxt){
		int v=node[i].to;
		if(v==father||v==son[u]) continue;
		for(int j=l[v]; j<=r[v]; ++j) Add(col[j]);
	}
	Add(tmp[u]);
	for(auto qry:querys[u]) ans[qry]=Getans();
	if(!keep){
		for(int j=l[u]; j<=r[u]; ++j) Del(col[j]);
	}
}
int n, m;
int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n;
	for(int i=1,u,v; i<n; ++i){
		cin>>u>>v; insert(u,v); insert(v,u);
	}
	for(int i=1; i<=n; ++i) cin>>tmp[i];
	cin>>m;
	for(int i=1; i<=m; ++i){
		int v; cin>>v; querys[v].push_back(i);
	}
	dfs1(1,1); solve(1,1,0);
	for(int i=1; i<=m; ++i) cout<<ans[i]<<'\n';
	return 0;
}

解釋一下我的代碼可能令人不解的點(diǎn)。

我們會(huì)發(fā)現(xiàn)我們需要不同的遍歷，為了更方便掃描子樹中的東西，我們使用 dfs 序來(lái)更簡(jiǎn)潔處理問(wèn)題。

這下明白 l, r 是什么意思了吧。

這個(gè)實(shí)現(xiàn)千奇百怪，但是并沒有什么難度，所以就不多說(shuō)了。

某些例題。

P9233 [藍(lán)橋杯 2023 省 A] 顏色平衡樹

題意

給你一顆節(jié)點(diǎn)數(shù)為 \(n\) 的樹，每個(gè)點(diǎn)有一個(gè)顏色，詢問(wèn)有多少節(jié)點(diǎn)滿足它子樹中各個(gè)顏色節(jié)點(diǎn)數(shù)相等。

我們還需要 \(O(n\log n)\) 左右的算法。

分析

詢問(wèn)子樹上的統(tǒng)計(jì)問(wèn)題，我們可以使用樹上啟發(fā)式合并，這個(gè)題還是很套路的。

如何快速判斷各個(gè)顏色數(shù)相等？我們記錄一下總共出現(xiàn)的顏色數(shù)和每個(gè)節(jié)點(diǎn)數(shù)的顏色數(shù)量就行，這兩個(gè)在樹上啟發(fā)式合并過(guò)程中維護(hù)就行，很簡(jiǎn)單，最后詢問(wèn)的時(shí)候我們利用所詢問(wèn)節(jié)點(diǎn)的顏色判斷即可。

算是板子，具體實(shí)現(xiàn)看一下代碼便懂了。

代碼

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=5e5+515;
struct Node{
    int nxt, to;
}node[MN];
int head[MN], tottt;
inline void insert(int u, int v){
    node[++tottt].to=v;
    node[tottt].nxt=head[u];
    head[u]=tottt;
    return;
}
int cntid[MN];//統(tǒng)計(jì)節(jié)點(diǎn)數(shù)量為i的顏色個(gè)數(shù)
int col[MN], tmp[MN];//存顏色的
int cntcol[MN], totcol;//統(tǒng)計(jì)一共有多少種顏色
void Add(int c){
    if(cntcol[c]==0) totcol++;
    cntcol[c]++;
    cntid[cntcol[c]-1]--;
    cntid[cntcol[c]]++;
}
void Del(int c){
    if(cntcol[c]==1) totcol--;
    cntcol[c]--;
    cntid[cntcol[c]+1]--;
    cntid[cntcol[c]]++;    
}
int Getsub(int u){
    int c=tmp[u];
    if(totcol==cntid[cntcol[c]]) return true;
    return false;
}
int depth[MN], fa[MN], siz[MN], son[MN], l[MN], r[MN];
int dfn_cnt;
void dfs1(int u, int father){
    fa[u]=father; depth[father]=depth[u]-1; siz[u]=1;
    l[u]=++dfn_cnt; col[dfn_cnt]=tmp[u];
    for(int i=head[u];i;i=node[i].nxt){
        int v=node[i].to;
        if(v==father) continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[son[u]]<siz[v]) son[u]=v;
    }
    r[u]=dfn_cnt;
}
int ans=0;
void dfs(int u, int father, bool keep){
    for(int i=head[u];i;i=node[i].nxt){
        int v=node[i].to;
        if(v==father||v==son[u]) continue;
        dfs(v,u,false);
    }
    if(son[u]) dfs(son[u],u,true);
    for(int i=head[u];i;i=node[i].nxt){
        int v=node[i].to;
        if(v==son[u]||v==father) continue;
        for(int j=l[v]; j<=r[v]; ++j){
            Add(col[j]);
        }
    }
    Add(tmp[u]);
    ans+=Getsub(u);
    if(!keep){
        for(int i=l[u]; i<=r[u]; ++i) Del(col[i]);
    }
}
int n;
signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin>>n;
    for(int i=1,c,father; i<=n; ++i){
        cin>>c>>father; tmp[i]=c;
        if(father) insert(i,father),insert(father,i);
    }
    dfs1(1,1);
    dfs(1,1,false);
    cout<<ans<<'\n';
    return 0;
}

CF375D Tree and Queries

這個(gè)也是同樣的簡(jiǎn)單，一個(gè)道理，我們使用 BIT 快速搞就行。

#include <bits/stdc++.h>
using namespace std;
const int MN=1e6+116;
struct Node{
	int nxt, to;
}node[MN];
int head[MN], tottt;
inline void insert(int u, int v){
	node[++tottt].to=v;
	node[tottt].nxt=head[u];
	head[u]=tottt; return;
}
int siz[MN], son[MN], col[MN];
int dfn_cnt, l[MN], r[MN], tmp[MN];
void dfs1(int u, int father){
	siz[u]=1; l[u]=++dfn_cnt; col[dfn_cnt]=tmp[u];
	for(int i=head[u]; i; i=node[i].nxt){
		int v=node[i].to;
		if(v==father) continue;
		dfs1(v,u); siz[u]+=siz[v];
		if(siz[son[u]]<siz[v]) son[u]=v;
	}
	r[u]=dfn_cnt;
}
int n, m, k, res=0;
int tr[MN], cnt[MN];
int lowbit(int x){
	return x&(-x);
}
void update(int pos, int val){
	for(int i=pos; i<MN; i+=lowbit(i)) tr[i]+=val; 
}
int qval(int pos){
	int res=0;
	for(int i=pos; i; i-=lowbit(i)) res+=tr[i];
	return res;
}
void Add(int col){
	if(cnt[col]) update(cnt[col],-1);
	cnt[col]++;
	if(cnt[col]==1) res++;
	update(cnt[col],1);
}
void Del(int col){
	update(cnt[col],-1);
	cnt[col]--;
	if(cnt[col]==0) res--;
	if(cnt[col]) update(cnt[col],1);
}
int Getans(int k){
	return qval(k-1);
}
struct Qrys{
	int id, k;
};
vector <Qrys> querys[MN];
int ans[MN];
void solve(int u, int father, int keep){
	for(int i=head[u];i;i=node[i].nxt){
		int v=node[i].to;
		if(v==father||v==son[u]) continue;
		solve(v,u,false);
	}
	if(son[u]) solve(son[u],u,true);
	for(int i=head[u];i;i=node[i].nxt){
		int v=node[i].to;
		if(v==father||v==son[u]) continue;
		for(int j=l[v]; j<=r[v]; ++j) Add(col[j]);
	}
	Add(tmp[u]);
	for(auto qry:querys[u]){
		ans[qry.id]=res-Getans(qry.k);
		//cout<<Getans(qry.k)<<'\n';
	}
	if(!keep){
		for(int j=l[u]; j<=r[u]; ++j) Del(col[j]);
	}
}
int main(){
	memset(cnt,0,sizeof(cnt));
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>m; for(int i=1; i<=n; ++i) cin>>tmp[i];
	for(int i=1,u,v; i<n; ++i){
		cin>>u>>v; insert(u,v); insert(v,u);
	}
	dfs1(1,1);
	for(int i=1; i<=m; ++i){
		int u, k; cin>>u>>k;
		querys[u].push_back({i,k});
	}
	solve(1,1,0);
	for(int i=1; i<=m; ++i) cout<<ans[i]<<'\n';
	return 0;
}
/*
10 2
75 72 81 90 62 39 32 88 61 58
2 1
3 2
4 3
5 1
6 4
7 1
8 4
9 6
10 8
2 99
2 68
*/

不太想寫了，這些題目的具體就是一些實(shí)現(xiàn)問(wèn)題罷了，所以我就懶得寫太多了

posted @ 2025-09-15 16:42 BaiBaiShaFeng 閱讀(17) 評(píng)論(0) 收藏舉報(bào)

刷新頁(yè)面返回頂部