模板
<pre><code class="language-cpp">//dsu on tree 大致框架
void dfs2(int u, int from, int opt){
int v;
for (int i = head[u];~i;i=edge[i].nxt){
if ((v=edge[i].to)==from || v==son[u]) continue;
dfs2(v, u, 0);//递归求解轻儿子答案
//删除轻儿子信息，也就对本树答案不做贡献
}
//开始对本树答案进行计算
//重儿子信息保留，也就对本树答案有贡献
if (son[u]) dfs2(son[u], u, 1);//对重儿子进行求解
//对轻儿子信息进行暴力统计
calc(u, from, son[u]);
//记录本树的答案
ans[u] = 统计后的信息;
//如果，当前树不是父亲的重儿子的话，需要删除本树所有信息
if (!opt) del(u, from);
}
//重链剖分部分，处理重儿子
void dfs1(int u, int from){
sz[u] = 1;//以当前节点为根节点的树大小
int v;
for (int i = head[u];~i;i=edge[i].nxt){
if ((v=edge[i].to)==from) continue;
dfs1(v, u);
//加上子树大小
sz[u] += sz[v];
//找到重儿子
if (sz[v]>sz[son[u]]){
son[u] = v;
}
}
}
</code></pre>