dsu on tree 模板 (树上启发式合并)

题目 题目 题意: T1:给定一棵n个点的树，求每个点以它为树根的子树的颜色种类。 T2:给定一棵n个点的树，求每个点以它为树根的子树的dominating color之和。 dominating color: 在本棵树中出现次数最多(或之一) 思路: dsu on tree，树上启发式合并，不过这个算法并没有用到dsu(并查集)。 考虑暴力求解，以每个点为起点dfs搜索一次，时间复杂度为n^2。 但是可以利用轻重链的性质，优化为nlogn。   注意到一个点的贡献是所有儿子求和，求完和儿子的贡献就用不到了。可以拿一个儿子的数组作为基点(就像并查集定一个点)，其他点向他合并。那么自然找重儿子作为基点。（因为重儿子的定义是它对应子树的大小是所有儿子里最大的(或之一)，至少占半壁江山）   而轻重链的性质决定了每个轻儿子到根节点的轻边个数不超过logn次。所以最多会被暴力合并logn次。轻儿子的子树大小