这两天看树上启发式合并。。

但是看得有些迷糊。

大概总结一下本人认为的算法流程：

1.一般开一个全局变量记录当前子树信息，先把轻儿子的信息处理了放在另外一个代表答案的数组里，然后清空这个全局变量。

2.然后找重儿子的信息，处理完后重儿子的信息在全局变量不用动，就是传递给了父节点。

3.最后合并所有轻儿子的信息到全局变量中，当做父节点的信息。

找了一些例题来看后，有些不理解。

就拿U41492来说，这个信息到底是怎么存下来的啊？

int dfs2(int u,int fa,int isson,int keep){
    if(keep){
        for(int i=head[u];i;i=t[i].nxt){
            int to=t[i].to;
            if(to!=fa&&to!=son[u]){
                dfs2(to,u,0,1);
            }
        }
    }
    int tmp=0;
    if(!keep&&son[u])tmp+=dfs2(son[u],u,1,0);
    else if(son[u]) tmp+=dfs2(son[u],u,1,1);
    for(int i=head[u];i;i=t[i].nxt){
        int v=t[i].to;
        if(v!=fa&&v!=son[u]){
            tmp+=dfs2(v,u,0,0);
        }
    }
    if(!cnt[c[u]]){
        tmp++;
    }
    cnt[c[u]]++;
    if(keep)ans[u]=tmp;
    if(keep&&!isson) memset(cnt,0,sizeof(cnt));
    return tmp;
}

合并这一步难道不需要遍历轻儿子的所有子节点吗？

话说为什么不把U41492转正成模板题呢？