被我暴力干过去了qwq。
你考虑一个事情,打开大样例,点击 .out 文件,发现几乎全是 \(0\),你想一想为什么,本质上是你的 \(mex\) 每增加 \(1\),你的点的数量就会至少翻一倍,也就是说,答案最多是 \(O(\log n)\) 级别的。
此时考虑直接设 \(f_{i, j}\) 为以 \(i\) 为根的子树进行完操作后有多少种满足 \(a_i = j\) 的,但是你发现这个转移不太好转。
没关系,先想暴力转移是,状压 DP,每次设一个 \(g_s\) 表示我的值的所用情况为 \(s\) 的方案数,然后你惊奇的发现这个 \(2^{ans}\) 正好和 \(O(\log n)\) 抵消掉了,所以答案就是 \(O(n^2 \log n)\) 的了(\(O(\log n)\) 是转移内部时间复杂度)。
然后此时加个只有一个儿子的特判,你就能通过此题了。
当然,还是要说明一下本题的正解。
考虑让重儿子单独合并,轻儿子按照我们上面的那个做法做,发现此时每做一次的时间复杂度为轻儿子的子树大小,由于一个点至多跳 \(O(\log n)\) 次,所以复杂度被优化到了 \(O(n \log^2 n)\)。
其实本质上就是类似折半合并的过程可以减少复杂度一样。