模板

//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;
        }
    }
}