Lomsat
CF600E Lomsat gelral
题意 给定一棵根为 \(1\) 的 有根树。 每个节点有颜色,求每个节点子树内出现最多的颜色编号之和。 Sol Dsu on tree板子题。 首先对于整棵树进行轻重链剖分,注意到一个关键性质:轻边只有 \(log\) 条。 \(n ^ 2\) 的暴力是 \(trivial\) 的,不再赘述。 注意 ......
CF600E Lomsat gelral
树上启发式合并(dsu on tree)通常用来查询不带修的子树信息,信息要求可合并。 对于一个结点 \(u\),其步骤如下: 求解其轻儿子的答案,同时清除递归产生的影响。 求解其重儿子的答案,保留递归产生的影响。 将轻儿子子树内的每个结点都合并进答案中,同时成为以 \(u\) 为根的子树产生的影响 ......