树上启发式合并（dsu on tree）

参考知乎Pecco树链剖分重子节点黑色实心 每个节点的孩子中子树大小最大的那个孩子。轻子节点白色空心 其他孩子。每条重链以轻子节点为开头轻子节点数重链数轻边数从一个父亲走到轻子节点因为重子节点的子树大小比其他轻子节点的子树大小都大轻子节点子树大小与父节点相比会至少减半。不断走轻边子树大小减半若树的大小为n最多能走l o g ( n ) log(n)log(n)次轻边从父节点走一次轻边到轻子节点相当于进入另一条重链。最多会有l o g ( n ) log(n)log(n)条重链。树上每个结点都属于且仅属于一条重链。思路dsu on tree利用重链剖分保留重儿子的计算结果暴力计算轻儿子的结果从而避免重复计算。是一种解决某些树上离线问题的算法尤其常被用于解决**“对每个节点询问关于其子树的某些信息”这样的问题。如果“子节点的某些信息”的规模较大简单的树形DP在时间和空间上都可能爆炸。所以我们不能存储每个节点的信息**而是要实现某种资源复用即只保留重儿子的信息把轻儿子及其子树的信息合并到重儿子记录的信息中这样得到整个子树的信息。每次轻儿子算两遍重儿子算一遍若总节点数为n轻子树最多合并log ⁡ n \log nlogn次时间复杂度O ( n log ⁡ n ) O(n\log n)O(nlogn)预处理树链剖分 寻找重儿子使用 predfs 进行一次 DFS。计算每个节点的子树大小 sz[u]。找出子树大小最大的儿子作为 hson[u]。主过程计算答案第一步处理轻儿子遍历所有非重儿子的子节点递归调用 dfs(v, u, 0)keep0这意味着这些轻儿子的计算结果不会保留只是向下找这些轻儿子的子树中的答案。第二步处理重儿子递归调用 dfs(hson[u], u, 1) keep1这意味着重儿子的计算结果cnt 数组会被保留下来作为当前子树的初始状态。第三步合并贡献将当前节点 u 加入统计add(u)。遍历所有轻儿子将它们的整棵子树贡献加入重子树的统计中addsubtree。此时cnt 数组中存储的就是以 u 为根的整棵子树的颜色统计信息。第四步清理现场如果 keep0说明当前子树是其父节点的轻儿子则需要清理掉整棵子树的影响delsubtree恢复 cnt 数组到进入 u 之前的状态以免干扰兄弟节点的计算。模板constintN2e510,M1e5;constdoublePIacos(-1);constlonglongmod998244353,inf1e18;vectorintg[N];intc[N];inthson[N],sz[N];// 找重子节点voidpredfs(intnow,intfa-1){sz[now]1;intszmx0;for(autox:g[now]){if(xfa)continue;predfs(x,now);sz[now]sz[x];if(szmxsz[x])szmxsz[x],hson[now]x;}}intcnt[N],ans[N],sm;// 将轻儿子添加到重儿子/// 计算答案voidadd(intnow){if(!cnt[c[now]])sm;// 有新的颜色cnt[c[now]];// 记录本颜色}voidaddsubtree(intnow,intfa){add(now);for(autox:g[now]){// if(xfa||xhson[now])continue;// 一开始这里写错了 应该把子树都放进去if(xfa)continue;addsubtree(x,now);}}// 如果keep0 把轻子树删掉 把cnt留给重子树voiddel(intnow){--cnt[c[now]];}voiddelsubtree(intnow,intfa){for(autox:g[now]){if(xfa)continue;delsubtree(x,now);}del(now);}// 主DFS找答案voiddfs(intnow,intfa-1,boolkeep1){// 遍历轻儿子 找轻儿子里面的答案for(autox:g[now]){if(xfa||xhson[now])continue;dfs(x,now,0);}// 走重儿子if(hson[now])dfs(hson[now],now,1);// 添加now和与其平行的轻儿子子树的答案因为此时重儿子子树已经添加进cnt中了 记录这个子树的答案add(now);for(autox:g[now]){if(xfa||xhson[now])continue;addsubtree(x,now);}ans[now]sm;// 轻儿子子树不保留if(!keep){delsubtree(now,fa);// 轻重子树都删sm0;}}voidsolve(){intn,m;cinn;forr(i,1,n-1){intu,v;cinuv;g[u].push_back(v);g[v].push_back(u);}forr(i,1,n){cinc[i];}predfs(1);dfs(1);cinm;// forr(i,1,n)coutans[i] ;coutendl;forr(i,1,m){intq;cinq;coutans[q]endl;}}例题CF600E题意给树的节点染色子树中出现最多次的颜色可能有多个称为占领该子树对每个节点求占领该节点所对应子树的颜色的编号之和。依旧统计子树颜色个数需要最多次的颜色只维护子树中最多次颜色的次数sum和颜色和res即可constintN2e510,M1e5;constdoublePIacos(-1);constlonglongmod998244353,inf1e18;vectorintg[N];intc[N];inthson[N],sz[N];// 找重子节点voidpredfs(intnow,intfa-1){sz[now]1;intszmx0;for(autox:g[now]){if(xfa)continue;predfs(x,now);sz[now]sz[x];if(szmxsz[x])szmxsz[x],hson[now]x;}}intcnt[N],ans[N],sm,res;// 将轻儿子添加到重儿子/// 计算答案voidadd(intnow){// 与模板相比需要改变add的计算逻辑cnt[c[now]];if(cnt[c[now]]sm)smcnt[c[now]],resc[now];elseif(cnt[c[now]]sm)resc[now];}voidaddsubtree(intnow,intfa){add(now);for(autox:g[now]){// if(xfa||xhson[now])continue;if(xfa)continue;addsubtree(x,now);}}// 如果keep0 把轻子树删掉 把cnt留给重子树voiddel(intnow){--cnt[c[now]];}voiddelsubtree(intnow,intfa){del(now);for(autox:g[now]){if(xfa)continue;delsubtree(x,now);}}// 主DFS找答案voiddfs(intnow,intfa-1,boolkeep1){// 遍历轻儿子 找轻儿子里面的答案for(autox:g[now]){if(xfa||xhson[now])continue;dfs(x,now,0);}// 走重儿子if(hson[now])dfs(hson[now],now,1);// 添加now和与其平行的轻儿子子树的答案因为此时重儿子子树已经添加进cnt中了 记录这个子树的答案add(now);for(autox:g[now]){if(xfa||xhson[now])continue;addsubtree(x,now);}ans[now]res;// 轻儿子子树不保留if(!keep){delsubtree(now,fa);// 轻重子树都删smres0;}}voidsolve(){intn;cinn;forr(i,1,n){cinc[i];}forr(i,1,n-1){intu,v;cinuv;g[u].push_back(v);g[v].push_back(u);}predfs(1);dfs(1);forr(i,1,n)coutans[i] ;coutendl;// forr(i,1,m){// int q;cinq;// coutans[q]endl;// }}蓝桥杯 颜色平衡树题意统计有多少个子树中每种颜色节点个数相同依旧颜色个数不过是所有的颜色个数相同可维护颜色个数最大值m x mxmx若满足条件子树大小 s z 节点数 × m x 子树大小sz节点数\times mx子树大小sz节点数×mxsz和mx都有了看颜色个数 m x 颜色个数mx颜色个数mx的节点数是否为子树节点数即可constintN2e510,M1e5;constdoublePIacos(-1);constlonglongmod998244353,inf1e18;vectorintg[N];intc[N];intsz[N],hson[N];voidpredfs(intnow){sz[now]1;intmx0;for(autox:g[now]){predfs(x);sz[now]sz[x];if(mxsz[x])mxsz[x],hson[now]x;}}intcnt[N],ans,mx,sm;voidadd(intnow){cnt[c[now]];if(cnt[c[now]]mx){mxcnt[c[now]];smcnt[c[now]];}elseif(cnt[c[now]]mx){smcnt[c[now]];}}voidaddsubtree(intnow){add(now);for(autox:g[now]){addsubtree(x);}}voiddelsubtree(intnow){cnt[c[now]]--;for(autox:g[now]){delsubtree(x);}}voiddfs(intnow,boolkeep1){// 轻for(autox:g[now]){if(xhson[now])continue;dfs(x,0);}// 重if(hson[now])dfs(hson[now],1);// 添轻add(now);for(autox:g[now]){if(xhson[now])continue;addsubtree(x);}// 记录答案if(smsz[now])ans;// 清空if(!keep)delsubtree(now),smmx0;}voidsolve(){intn;cinn;forr(i,1,n){intf;cinc[i]f;g[f].push_back(i);}predfs(1);dfs(1);coutansendl;}