被我暴力干过去了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)\)。
其实本质上就是类似折半合并的过程可以减少复杂度一样。