CF442D Adam and Tree

有生之年独立做出来的黑题（至少现在是）。

首先，一定有一种最优情况使得一条颜色的路径不会同时包含某个节点的多于一个儿子。

证明：如果有存在同时包含某个节点多于一个儿子的路径，那么由于我们只关心某个节点到根节点的颜色数量，而不关心总颜色数量，因此将这条路径拆成两条即可。

然后考虑设 $f_u$ 表示以 $u$ 为根的子树，包括其连向父亲的那条边的最优解。

考虑到我们现在要给 $u\rightarrow fa_u$ 染色，那么我们应当将其染成儿子的最大值的颜色。因为这样一定可以尽量减少对答案的贡献。那么儿子的次大值就会加上 $1$。因此我们同时维护最大值 $max1$，次大值 $max2$，可以得到转移方程：

$$f_u=\max\{max1_u, max2_u+1\}$$

考虑这样暴力转移是 $O(n)$ 的，总时间复杂度 $O(n^2)$。

我们加入这样一个优化：如果加入一个节点，向上更新的过程中，发现已经无法更新该节点，那么就直接停止更新。这样的时间复杂度是 $O(n\log n)$ 的。

为什么呢？因为可以发现，我们每次更新的一定是一条链。而我们染色的过程类似于重链剖分，一个节点到根的过程经过的链的数量是 $O(\log n)$ 的，因此总时间复杂度 $O(n\log n)$。

void dfs(int u)
{
    if(u == 0) return;
    if(max1[fa[u]] < f[u])
    {
        max2[fa[u]] = max1[fa[u]];
        max1[fa[u]] = f[u];
    }
    else if(max2[fa[u]] < f[u])
    {
        max2[fa[u]] = f[u];
    }
    int ans = max(max1[fa[u]], max2[fa[u]] + 1);
    if(f[fa[u]] == ans) return;
    f[fa[u]] = ans;
    dfs(fa[u]);
}

signed main()
{
    read(n);
    f[1] = 1;
    for(int i = 2; i <= n + 1; i++)
    {
        f[i] = 1;
        fa[i] = read();
        dfs(i);
        printf("%d ", max1[1]);
    }
    return 0;
}