1740H

CF1740H MEX Tree Manipulation 定义一棵树上每个节点的值为其所有儿子的值的 MEX，叶子节点的值为 \(0\)。 现在有一个初始只有节点 \(1\) 的树，每次输入一个 \(x_i\) 代表加入一个点 \(i+1\)，它的父亲为 \(x_i\)，求加入这个点之后树上所有点 ......

首先发现一个性质，那就是每个点的点权是 $\log n$ 级别的。因为假设要造出一个点权为 $i$ 的点至少需要大小为 $mn_i$ 的子树，那么显然有 $mn_i=\sum\limits_{j=0}^{i-1}mn_j+1$，即 $mn_i=2^i$。 由于点权不是很大，因此我们很容易地往变换复合 ......