树剖+构造 t3 O(n)做法

本人赛时思路如下：

首先，本题在本人眼中有两个重要的性 质： 1，将mex=0的点定义为无用的点，每个有用点的贡献为其子树大小。

因为一个点的s集合为子树中所有点的赋值集合，且该点的贡献为集合的mex值，如果钦定该点做贡献，则需要使该点mex最大，即让其子树中的所有点取值集合为0，1，2...到该点的子树大小-1，则该点的贡献为该点的子树大小。

这就相当于我们强制把重儿子子树之外的所有点的贡献强制置为0。 2，为了让最终得到的mex之和最大，我们应当选择重儿子进行贡献，因为他们子树大小最大。

做法如下。

我们要最大化这类点的贡献，等同于最大化这类点的子树大小。这个我会啊！重链剖分找重儿子呗！然后我写了几个O(n)的dfs找出了每个点的深度dep[u],重儿子heavy_son[u],子树大小siz[u]。 最大的子树必定存在于重链上，每个重儿子所做的贡献大小必定等于其子树大小，所以我们再用另一个dfs从根节点开始向下遍历重儿子的子树大小，最后累加起来即为答案。

可能是错误思路，考场上样例2过不了。本人已尽力。