先瞎扯幾句
說起來我跟這個算法好像還有很深的淵源呢qwq。當時在學業水準考試的考場上，題目都做完了不會做，于是開始xjb出題。突然我想到這麼一個題
看起來好像很可做的樣子，然而直到考試完我都隻想出來一個莫隊的暴力。當時我想知道有沒有比莫隊更優的做法，和zbq讨論了半天也隻能搞出一個$O(nlog^2n)$的平衡樹啟發式合并
然後！！我就把這題出給校内互測了！！沒錯，當時是用莫隊當的标算！
結果！mjt用一個假的$O(n)$算法艹過去了因為資料特别水
後來我打算把這題出給另一場比賽，結果到了前一天晚上造資料的時候我發現不太對，然後把mjt的算法hack了。
去UOJ群裡一問才知道這玩意兒是個dsu on tree的sb題。
當時我就這個表情
自己還是太年輕啊%>_<%
好了好了，來講算法吧
Dsu on tree
簡介
dsu on tree跟dsu(并查集)是沒啥關系，可能是借用了一波啟發式合并的思想？？
它是用來解決一類樹上詢問問題，一般這種問題有兩個特征
1、隻有對子樹的詢問
2、沒有修改
一般這時候就可以強上dsu on tree了
update：可能特征1不會很顯然，就是說題目中不一定明确的問你子樹$i$的答案，可能是把問題轉化後需要算子樹$i$的答案
算法流程
考慮暴力怎麼寫：周遊每個節點—把子樹中的所有顔色暴力統計出來更新答案—消除該節點的貢獻—繼續遞歸
這肯定是$O(n^2)$的。
dsu on tree巧妙的利用了輕重鍊剖分的性質，把複雜度降到了$O(nlogn)$
啥啥啥？你不知道啥叫輕重鍊剖分？
一句話：對于樹上的一個點，與其相連的邊中，連向的節點子樹大小最大的邊叫做重邊，其他的邊叫輕邊
dsu on tree的算法流程是這樣的：
對于節點$i$：
- 周遊每一個節點
- 遞歸解決所有的輕兒子，同時消除遞歸産生的影響
- 遞歸重兒子，不消除遞歸的影響
- 統計所有輕兒子對答案的影響
- 更新該節點的答案
- 删除所有輕兒子對答案的影響
主體架構長這樣
可能你先在會想：為什麼都是暴力統計答案？這樣複雜度不是$O(n^2)$的麼？
那簡單的來證一下這東西的複雜度
複雜度
性質：一個節點到根的路徑上輕邊個數不會超過$logn$條
證明：
設根到該節點有$x$條輕邊，該節點的大小為$y$，根據輕重邊的定義，輕邊所連向的點的大小不會成為該節點總大小的一般。
這樣每經過一條輕邊，$y$的上限就會$ / 2$，是以$y < \frac{n}{2^x}$
因為$n > 2^x$，是以$x < logn$
然而這條性質并不能解決問題。
我們考慮一個點會被通路多少次
一個點被通路到，隻有兩種情況
1、在暴力統計輕邊的時候通路到。
根據前面的性質，該次數$< logn$
2、通過重邊 / 在周遊的時候被通路到
顯然隻有一次
如果統計一個點的貢獻的複雜度為$O(1)$的話，該算法的複雜度為$O(nlogn)$
模闆題
cf600E. Lomsat gelral
題意：給出一個樹，求出每個節點的子樹中出現次數最多的顔色的編号和
dsu on tree的模闆題，暴力統計即可
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN = 1e5 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, col[MAXN], son[MAXN], siz[MAXN], cnt[MAXN], Mx, Son;
LL sum = 0, ans[MAXN];
vector<int> v[MAXN];
void dfs(int x, int fa) {
siz[x] = 1;
for(int i = 0; i < v[x].size(); i++) {
int to = v[x][i];
if(to == fa) continue;
dfs(to, x);
siz[x] += siz[to];
if(siz[to] > siz[son[x]]) son[x] = to;//輕重鍊剖分
}
}
void add(int x, int fa, int val) {
cnt[col[x]] += val;//這裡可能會因題目而異
if(cnt[col[x]] > Mx) Mx = cnt[col[x]], sum = col[x];
else if(cnt[col[x]] == Mx) sum += (LL)col[x];
for(int i = 0; i < v[x].size(); i++) {
int to = v[x][i];
if(to == fa || to == Son) continue;
add(to, x, val);
}
}
void dfs2(int x, int fa, int opt) {
for(int i = 0; i < v[x].size(); i++) {
int to = v[x][i];
if(to == fa) continue;
if(to != son[x]) dfs2(to, x, 0);//暴力統計輕邊的貢獻，opt = 0表示遞歸完成後消除對該點的影響
}
if(son[x]) dfs2(son[x], x, 1), Son = son[x];//統計重兒子的貢獻，不消除影響
add(x, fa, 1); Son = 0;//暴力統計所有輕兒子的貢獻
ans[x] = sum;//更新答案
if(!opt) add(x, fa, -1), sum = 0, Mx = 0;//如果需要删除貢獻的話就删掉
}
int main() {
N = read();
for(int i = 1; i <= N; i++) col[i] = read();
for(int i = 1; i <= N - 1; i++) {
int x = read(), y = read();
v[x].push_back(y); v[y].push_back(x);
}
dfs(1, 0);
dfs2(1, 0, 0);
for(int i = 1; i <= N; i++) printf("%I64d ", ans[i]);
return 0;
} 一道比較有意思的題
不知道老師從哪兒弄的。。。
我的題解：https://www.cnblogs.com/zwfymqz/p/9687296.html
官方題解：
參考資料
[Codeforces600E]Lomsat gelral（dsu on the tree）
[trick]dsu on tree
作者：自為風月馬前卒
個人部落格http://attack204.com//
出處：http://zwfymqz.cnblogs.com/
本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。