CF1981F

出题人题解。

Sol 1

首先有个一定需要的 $O(n^2)$ dp：设 $dp_{u,i}$ 表示当前在 $u$ 点，钦定选的链上点权一定不包含 $i$，此时的最小代价。转移是非常简单的，只要看当前链是否在这里断开即可。而且 $\operatorname{mex}$ 性质是很好的，如果此时转移的 $i$ 并不是 $\operatorname{mex}$，也一定不会成为最优解，而是真正的 $\operatorname{mex}$ 会成为最优解。于是这么做是正确的。

然后会观察出一个问题：我们很多时候并不会取到很大的 $\operatorname{mex}$。然而，我们 dp 的第二位就是和这个上界相关。而根据证明（参考 cf 上的 edtorial），这个上界是 $O(\dfrac{n}{\ln n})$ 的！我们也可以通过一个构造证明：12131421516321，即把每个数和它的因数降序列出。感性理解一下发现很有道理。你考虑分成 $n$ 组。对于每个数 $x$，你都会希望每 $x$ 长度就有一个 $x$，否则消耗了这么多的长度会亏。并且通过提交证明这是对的。

于是就限制第二维枚举到大概 $4000$，就可以 $O(\dfrac{n^2}{\ln n})$ 解决了。

code：

bool Mbe;
int n,m,c[N],dp[N][M],ls[N],rs[N];
void dfs(int u){
    if(!u){
        return;
    }
    dfs(ls[u]),dfs(rs[u]);
    if(!ls[u]&&!rs[u]){
        rep(i,1,m){
            if(i!=c[u]){
                dp[u][i]=0;
            }
        }
        if(u==1){
            puts("0");
        }
        return;
    }
    if(!rs[u]){
        int mn=inf;
        rep(i,1,m){
            if(i!=c[u]){
                dp[u][i]=dp[ls[u]][i];
                mn=min(mn,dp[u][i]+i);
            }
        }
        rep(i,1,m){
            if(i!=c[u]){
                dp[u][i]=min(dp[u][i],mn);
            }
        }
        if(u==1){
            printf("%d\n",mn);
        }
        return;
    }
    int x=inf,y=inf,mn=inf;
    rep(i,1,m){
        if(i!=c[u]){
            x=min(x,dp[ls[u]][i]+i);
            y=min(y,dp[rs[u]][i]+i);
        }
    }
    rep(i,1,m){
        if(i==c[u]){
            continue;
        }
        mn=min(mn,dp[ls[u]][i]+dp[rs[u]][i]+i);
        dp[u][i]=min({dp[u][i],dp[ls[u]][i]+y,dp[rs[u]][i]+x});
    }
    rep(i,1,m){
        if(i!=c[u]){
            dp[u][i]=min(dp[u][i],mn);
        }
    }
    if(u==1){
        printf("%d\n",min(mn,x+y));
    }
}
void Yorushika(){
    scanf("%d",&n),m=min(n+1,4000);
    rep(i,1,n){
        scanf("%d",&c[i]);
        rep(j,1,m){
            dp[i][j]=inf;
        }
        ls[i]=rs[i]=0;
    }
    rep(i,2,n){
        int u;scanf("%d",&u);
        if(ls[u]){
            rs[u]=i;
        }else{
            ls[u]=i;
        }
    }
    dfs(1);
}
bool Med;
signed main(){
	cerr<<(&Mbe-&Med)/1048576.0;
    int t=1;
        scanf("%d",&t);
    while(t--)
        Yorushika();
}

Sol 2

先有 $O(n^2)$ dp，然后观察到一个性质：对于所有没在以 $u$ 为根的子树内出现过的点权 $x$，$dp_{u,x}$ 都是相等的！原因显然。而且我们 dp 的转移是非常好维护的，于是可以使用线段树合并或启发式合并解决。时间复杂度 $O(n\log n)$ 或 $O(n\log^2 n)$。

可以参考 AFewSuns 的代码。

完整：

好像被骂难了，但是我主观上认为，作为一个 F 题，放一道更有新意，有难度的问题远比放一道板子之流有意义得多，即使没人做出来。我相信高水平选手应该更注重问题本身，而不是比赛如何如何，既然只是一场 CF。

说回正题。讲讲这个问题出现的过程。

一开始是出来作 D 的，想的是一个完全暴力的指数级做法。结果被 co 一眼秒了 $O(n^2)$ 做法：

设 $dp_{u,i}$ 表示当前在 $u$ 点，钦定选的链上点权一定不包含 $i$，此时的最小代价。转移是非常简单的，只要看当前链是否在这里断开即可。而且 $\operatorname{mex}$ 性质是很好的，如果此时转移的 $i$ 并不是 $\operatorname{mex}$，也一定不会成为最优解，而是真正的 $\operatorname{mex}$ 会成为最优解。于是这么做是正确的。

顺便一提，这使我想起了 candles，感觉有异曲同工之妙啊！

于是我们决定 F 就放这个 $O(n^2)$ 的 dp 问题。但此时发生了两件事：一是，我们发现 $O(n^3)$ dp，也就是存链的底端是什么，然后计算链上 $\operatorname{mex}$ 转移的暴力 dp，我们卡不掉。二是 co 问我们，是否能构造出最优情况下选择的链中 $\operatorname{mex}$ 尽可能大的数据。

经过一番思考，设 $\operatorname{mex}=m$，我们很快得到了一个 $m\sqrt m=n$ 的构造：121321432154321...。但是过了几天，zlt 说他有了一种更强的构造：12131421516321，即把每个数和它的因数降序列出。感性理解一下发现很有道理。你考虑分成 $n$ 组。对于每个数 $x$，你都会希望每 $x$ 长度就有一个 $x$，否则消耗了这么多的长度会亏。并且通过提交证明这是对的。

然后 zlt 再通过更严谨的证明得出确实就有 $m\ln m=n$，也就大概有 $m=\dfrac{n}{\ln n}$。于是，就有了这个奇怪的范围和这道有点毒瘤的题。

然后在比赛的前一周，我还是对这个题比较担心。于是问 zlt 能否问 AFewSuns 来验一下 F。结果 afs 秒了 $O(n^2)$，过了一会儿说会 $n\operatorname{poly} \log$ 了：对于所有在以 $u$ 为根的子树内没有出现过的点权 $x$，$dp_{u,x}$ 是相等的。于是就有了启发式合并的做法。然后我随口问了句线段树合并是否可行，结果过了两天，crazy_sea 看了这题，然后秒了 $O(n\log n)$ 线段树合并。/bx/bx/bx

虽然爆标了，但是介于这种做法代码难度很大，而且常数大，于是没有修改范围。

总结：我啥都没干（bushi）