600e

题意 给定一棵根为 \(1\) 的 有根树。 每个节点有颜色，求每个节点子树内出现最多的颜色编号之和。 Sol Dsu on tree板子题。 首先对于整棵树进行轻重链剖分，注意到一个关键性质：轻边只有 \(log\) 条。 \(n ^ 2\) 的暴力是 \(trivial\) 的，不再赘述。 注意 ......

树上启发式合并（dsu on tree）通常用来查询不带修的子树信息，信息要求可合并。 对于一个结点 \(u\)，其步骤如下： 求解其轻儿子的答案，同时清除递归产生的影响。 求解其重儿子的答案，保留递归产生的影响。 将轻儿子子树内的每个结点都合并进答案中，同时成为以 \(u\) 为根的子树产生的影响 ......

题目链接：https://codeforces.com/problemset/problem/600/E 这是一道树上启发式合并的题，就只是在模板的基础上稍微变化了一下 解题思路:我们需要计算当前u节点的答案，要计算加入非重链节点对此答案的影响，在计算加入节点对ans影响的时候，遍历u除了重链外的所 ......