树上启发式合并待补

本文主要是介绍树上启发式合并待补，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

对于每个子树，直接遍历所有轻儿子，继承重儿子
会了板子后，修改维护的东西和莫队是一样的

洛谷 U41492

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
constexpr int N=1e5+5;
std::vector<int> e[N];
int c[N],sum[N],ans[N],dfn[N],dfncnt,sz[N],node[N],son[N],tol;void add(int x){if (sum[c[x]]==0){tol++;}sum[c[x]]++;
}
void del(int x){sum[c[x]]--;if (sum[c[x]]==0){tol--;}
}
void dfs1(int u,int fa){dfn[u]=++dfncnt;node[dfncnt]=u;sz[u]=1;int maxson=0;for (auto v:e[u]){if (v==fa) continue;dfs1(v,u);sz[u]+=sz[v];if (maxson<sz[v]){son[u]=v;maxson=sz[v];}}
}
void dfs2(int u,int fa,bool keep){for (auto v:e[u]){if (v==fa||v==son[u]) continue;dfs2(v,u,0);}if (son[u]){dfs2(son[u],u,1);}for (auto v:e[u]){if (v==fa||v==son[u]) continue;for (int i=dfn[v];i<=dfn[v]+sz[v]-1;i++){add(node[i]);}}add(u);ans[u]=tol;if (!keep){for (int i=dfn[u];i<=dfn[u]+sz[u]-1;i++){del(node[i]);}}
}
void yrzr(){int n;std::cin>>n;for (int i=1;i<n;i++){int x,y;std::cin>>x>>y;e[x].push_back(y);e[y].push_back(x);}for (int i=1;i<=n;i++){std::cin>>c[i];}dfs1(1,0);dfs2(1,0,1);int m;std::cin>>m;while (m--){int x;std::cin>>x;std::cout<<ans[x]<<"\n";}
}
int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int T=1;// std::cin>>T;while (T--){yrzr();}return 0;
}

CF600E
板子，改一下修改操作就行了

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
constexpr int N=1e5+5;
std::vector<int> e[N];
int c[N],dfn[N],dfncnt,son[N],sz[N],sum[N],node[N],maxn;
ll tol[N],ans[N];
void add(int x){x=c[x];tol[sum[x]]-=x;sum[x]++;tol[sum[x]]+=x;maxn=std::max(maxn,sum[x]);
}
void del(int x){x=c[x];tol[sum[x]]-=x;sum[x]--;tol[sum[x]]+=x;if (maxn==sum[x]+1&&tol[sum[x]+1]==0){maxn--;}
}
void dfs1(int u,int fa){dfn[u]=++dfncnt;node[dfncnt]=u;sz[u]=1;int maxson=0;for (auto v:e[u]){if (v==fa) continue;dfs1(v,u);sz[u]+=sz[v];if (maxson<sz[v]){son[u]=v;maxson=sz[v];}}
}
void dfs2(int u,int fa,bool keep){for (auto v:e[u]){if (v==fa||v==son[u]) continue;dfs2(v,u,0);}if (son[u]){dfs2(son[u],u,1);}for (auto v:e[u]){if (v==fa||v==son[u]) continue;for (int i=dfn[v];i<=dfn[v]+sz[v]-1;i++){add(node[i]);}}add(u);ans[u]=tol[maxn];if (!keep){for (int i=dfn[u];i<=dfn[u]+sz[u]-1;i++){del(node[i]);}}
}
void yrzr(){int n;std::cin>>n;for (int i=1;i<=n;i++){std::cin>>c[i];}for (int i=1;i<n;i++){int x,y;std::cin>>x>>y;e[x].push_back(y);e[y].push_back(x);}dfs1(1,0);dfs2(1,0,1);for (int i=1;i<=n;i++){std::cout<<ans[i]<<" ";}
}
int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int T=1;// std::cin>>T;while (T--){yrzr();}return 0;
}