【学习笔记】神(奇)奇(技)思(淫)路(巧)
本篇是关于我做题时遇到的很神奇的技巧和思路的总结，会不定时更新
树上启发式合并
问题描述：
有一类问题是关于统计树上每个子树的某些信息，而且这些信息不支持高效合并，也就是说必须暴力整个子树才能得到答案。
方法总结：
最暴力的思路就是从根开始一棵一棵子树进行访问，访问完一棵子树清空一次我们统计的信息然后访问下一棵子树，子树全部搞完了就访问以当前点为根的树。我们会发现对于最后一棵子树的信息我们可以不清空，因为这棵子树的信息完全可以累加到我们的整棵树上，这样就可以少访问一棵子树，那么我们就考虑怎么做能让访问次数最少。很明显：让不清空信息的子树成为重儿子的那棵子树，即子树大小最大的那棵子树。
也就是：访问所有非重儿子的子树统计信息并清空，访问重儿子的子树然后将信息合并到整棵树上再访问整棵树的信息。
复杂度证明：
我们将连接重儿子的边称为重边，其他边称为轻边。那么对于节点 \(i\)，他被访问的次数就是它到根上轻边的数量加一，而根到任何一个点的轻边数量不超过 \(\log n\) 条。因为对于轻边连接的儿子来说，每次它的子树大小至少会乘二，所以最多 \(\log n\) 次就结束了。
所以树上启发式合并的复杂度为： \(O(n \log n)\)
例题：
CF600E Lomsat gelral
代码：
点击查看代码
#include
using namespace std;
const long long MAXN = 1e5+5;
const long long MAXM = 2 * MAXN;
struct edge{
long long nxt,to;
edge(){}
edge(long long _nxt,long long _to){
nxt = _nxt,to = _to;
}
}e[MAXM];
long long tot,mx,sum,head[MAXN],sz[MAXN],son[MAXN],color[MAXN],cnt[MAXN],ans[MAXN];
void add_edge(long long from,long long to){
e[++tot] = edge(head[from],to);
head[from] = tot;
}
void get_son(long long now,long long fa){ //获取子树大小以及重儿子
sz[now] = 1;
long long maxn = 0;
for(long long i=head[now]; i; i = e[i].nxt){
long long to = e[i].to;
if(to == fa) continue;
get_son(to,now);
if(sz[to] > sz[maxn]){
maxn = to;
}
sz[now] = sz[now] + sz[to];
}
son[now] = maxn;
}
void get_ans(long long now,long long fa,long long heavy_son){ //暴力 dfs 当前子树的信息，除去重儿子
cnt[color[now]]++;
if(cnt[color[now]] > mx){
mx = cnt[color[now]];
sum = color[now];
}
else if(cnt[color[now]] == mx){
sum += color[now];
}
for(long long i=head[now]; i; i = e[i].nxt){
long long to = e[i].to;
if(to == fa || to == heavy_son) continue;
get_ans(to,now,heavy_son);
}
}
void clear(long long now,long long fa){ //清空当前子树的信息
cnt[color[now]]--;
for(long long i=head[now]; i;i = e[i].nxt){
long long to = e[i].to;
if(to == fa) continue;
clear(to,now);
}
}
void dfs(long long now,long long fa){ //启发式合并的过程
for(long long i=head[now]; i;i = e[i].nxt){
long long to = e[i].to;
if(to == fa || to == son[now]) continue;
dfs(to,now);
clear(to,now);
sum = mx = 0;
}
if(son[now]){ //重儿子不清空
dfs(son[now],now);
}
get_ans(now,fa,son[now]);
ans[now] = sum;
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
long long n;
cin>>n;
for(long long i=1; i<=n; i++){
cin>>color[i];
}
for(long long i=1; i>from>>to;
add_edge(from,to);
add_edge(to,from);
}
get_son(1,0);
dfs(1,0);
for(long long i=1; i<=n; i++){
printf("%lld ",ans[i]);
}
return 0;
}