题解：CF2254G Nightcrawler

TrueGod · 2026-11-10 20:30:09 · 题解

似乎爆标了？

从 k=n 倒着考虑，猜测 k 的答案可以通过 k+1 的答案中合并两个集合得到。

对于两个集合 S,T，记两个集合中深度最深的点分别为 u,v，则 S 能够和 T 合并当且仅当 u,v 之间存在祖先关系。所以我们只关心一个集合最深的结点 u，和这个集合的权值 w(u)。

那么现在问题变为，每次可以选择一对存在祖先关系的 (u,v)，设 w(u)\le w(v)，先让答案减去 w(u)，如果 u 是 v 的祖先，则将 u 删除，否则将 v 删除并令 w(u)\gets w(v)。因为我们想要答案最大，所以每次贪心的选择 w(u) 最小的 u，然后选择一个最优的 v 来进行操作。

什么样的 v 才是最优的呢？贪心地，优先选择 v 在 u 子树内，否则选择 u 的未被删除的最近祖先。感性理解一下，这样子在删除 u 或 v 后被影响的点的数量是最少的。如果不存在这样的 v 就可以跳过当前的 u 继续这个过程，如果所有 u 都被跳过则答案就是 -1。

::::info[AI 提供的严格证明]

如何选择与 u 合并的点？

先把已经删除的点忽略。对于每个剩余点，把它最近的、仍未被删除的祖先视为父亲，这样剩余点就构成了一片森林。

注意，这只是为了方便理解，实际实现时不需要真的维护这片森林。

情况一：u 还有后代

这时，与任意一个仍存在的后代 v 合并都可以。

因为我们选择的是权值最小的可合并点 u，所以 w(u)\le w(v)。操作之后，只是删除了 u，其他点的位置和权值都没有改变。

也就是说，无论选择哪个后代，操作后的状态都完全一样，因此不需要纠结应该选择哪个后代。

情况二：u 没有后代，但还有祖先

这时，选择 u 最近的、仍存在的祖先 v，也就是当前森林中 u 的父亲。

合并之后，删除 v，并令。

w(u)\gets w(v)

这里不能随便选择一个祖先，必须保证我们下面证明所用的“最近祖先”性质。

情况三：u 既没有祖先，也没有后代

这说明 u 已经无法与任何其他集合合并。

而且，后续操作只会删除点、修改权值，不会让两个原本没有祖先关系的点突然产生祖先关系。因此，u 以后也不可能参与合并，可以把它从维护的数据结构中移除。

注意，这里只是不再考虑它，并不是把它对应的集合删掉：它的权值仍然要计入答案。

因此，我们每次实际选择的，是所有还能参与合并的点中，权值最小的那个点。

为什么这样贪心是对的？

我们证明一个比“这一步最优”更强的结论：

假设当前还有 m 个集合。按照上述规则合并一次后，对于任意 k<m，都不会失去得到最优 k 集合划分的机会。

换句话说，这一步合并不仅保住了 m-1 个集合时的答案，也同时保住了所有更小的 k 的答案。

为了方便表述，下面把满足祖先关系的集合称为一条“链”。这里的链不要求包含路径上的所有点。

一个小结论：拆开一条链，能增加多少分？

设 u 是当前权值最小的可合并点。

对于任意一条包含至少两个点的链，保留一个最大值在原链中，再把另一个点 x 拆出来单独成链。

这样，原链的得分不变，又多出了一条得分为 w(x) 的链，总分增加了 w(x)。

由于 x 位于一条多点链中，它一定是可合并点，所以。

w(x)\ge w(u)

因此：

拆开一条多点链，可以让链数增加 1，并且让总分至少增加 w(u)。

这个结论可以用来补偿删除一条权值为 w(u) 的单点链所造成的损失。

证明一：u 有后代时，可以直接删除 u

固定任意一个 k<m，考虑当前问题的一个最优 k 链划分。

分两种情况。

1. u 所在的链不止一个点

直接把 u 从链中删掉即可。

因为 u 是权值最小的可合并点，而同链的其他点也都是可合并点，所以删除 u 不会改变这条链的最大值。

链数不变，总分也不变。

2. u 单独成链

删除这条单点链之后：

链数减少 1；
总分减少 w(u)。

但当前有 m 个点，却只分成 k<m 条链，所以一定存在另一条多点链。

将那条链拆开，就能把链数补回来，并且至少补回 w(u) 的分数。

所以，删除 u 后，仍然能得到一个不劣的 k 链划分。

反过来，对于删除 u 后的任意划分，我们都可以把 u 加到某个后代 v 所在的链中：

这条链仍然合法；
因为 w(u)\le w(v)，得分不变。

于是，删除 u 前后，最优 k 链划分的得分完全相同。

而且，这里的 v 可以是任意一个仍存在的后代，所以有后代时确实不需要特别挑选合并对象。

证明二：u 没有后代时，可以与最近祖先合并

设 v 是 u 最近的、仍存在的祖先。

我们要证明：

对于任意 k<m，都存在一个最优 k 链划分，使得 u,v 位于同一条链中。

这样就可以放心地先合并 u,v。

这里有一个非常重要的性质：

在不包含 v 的情况下，任何与 u 同链的其他点，都一定在 v 上方。

这是因为：

现在取一个最优 k 链划分。如果 u,v 已经同链，就没有什么需要证明的了。

否则，设：

下面把这两条链稍作调整，让 u,v 进入同一条链，并保证总分不下降。

1. v 不是链 D 的最大值，即 w(v)<M_D

直接把 v 从 D 移到 C。

从 D 中拿走的不是最大值，所以 D 的得分不变。
给 C 加入一个点，得分当然不会下降。

这样就让 u,v 同链了。

2. v 是链 D 的最大值，即 w(v)=M_D

如果 C,D 不全是单点链，就把它们重新分成：

C'=\{u,v\}, D'=(C\cup D)\setminus\{u,v\}

也就是让 u,v 单独组成一条链，把原来的其他点放在另一条链中。

先看合法性。

所以，这些剩余点放到一起，仍然是一条合法的链。

再看得分。

新链 C' 的得分为。

\max(w(u),w(v))=w(v)=M_D

而新链 D' 的得分至少为 M_C：

如果 C 不止一个点，删掉最小的 u，不会丢掉 C 的最大值；
如果 C=\{u\}，那么 D' 非空，其中任意一个点的权值都至少为 w(u)=M_C。

因此，新得分至少为。

M_D+M_C

不小于原得分。

3. C=\{u\}，D=\{v\}

此时直接合并这两条单点链，会让链数减少 1，总分减少 w(u)。

但由于 k<m，一定还有另一条多点链。将其拆开，既能恢复链数，也至少能补回 w(u) 的分数。

所以，这种情况也能调整成一个不劣的划分，使 u,v 同链。

综上，总能找到一个最优划分，让 u 与最近祖先 v 同链。因此，可以先把它们合并，保留 u，并令。

w(u)\gets w(v)

从局部操作得到所有答案

现在，最开始的猜测就得到了证明。

初始时，每个点单独成集，所以。

\operatorname{ans}_n=\sum_{i=1}^{n}a_i

每次选择权值最小的可合并点 u，按上述规则合并，令当前总分减去 w(u)。

由于每次合并都不会影响所有更小集合数的最优答案，所以，当集合数降到 k 时，当前总分就是 \operatorname{ans}_k。

如果已经不存在能够合并的点对，那么当前所有代表点之间都没有祖先关系，无法继续减少集合数，剩余答案全部为 -1。

现在我们需要支持删除一个点 u，查询 u 子树内是否有未被删除的结点，查询 u 的最近未被删除祖先。可以使用并查集解决。具体地，显然只要 u 不是原树叶子那么 u 子树内一定有点，否则一定没点；并查集内直接维护 u 的最近祖先，每次删除点 u 时就将 u 所在连通块与 u 的父亲所在连通块合并。

最后我们发现每次取出 w(u) 最小的 u 只需要一开始排一次序即可。排序部分使用基数排序，最终复杂度 \mathcal{O}(n\alpha(n))。

这份代码加上快读后可以获得 CF 上的所有语言最优解。

#include<bits/stdc++.h>
using namespace std;using ll=long long;
const int N=200005;int a[N],p[N],pos[N],id[N],tmp[N],c[1024];ll ans[N];
struct DSU{
    int f[N],top[N];
    void init(int n){fill(f,f+n+1,-1),iota(top,top+n+1,0);}
    int find(int x){for(;f[x]>=0;x=f[x])if(f[f[x]]>=0)f[x]=f[f[x]];return x;}
    void del(int x,int y){y=find(y);int t=top[y];if(f[x]>f[y])swap(x,y);f[x]+=f[y],f[y]=x,top[x]=t;}
}d;
void solve(){
    int n,mx=0;cin>>n;ll sum=0;
    for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i],mx=max(mx,a[i]),pos[i]=id[i-1]=i;
    for(int i=2;i<=n;i++)cin>>p[i],pos[p[i]]=0;
    int *q=id,*r=tmp;
    if(n<=64)sort(q,q+n,[](int x,int y){return a[x]<a[y];});
    else for(int s=0;s<30&&(mx>>s);s+=10){
        fill(c,c+1024,0);
        for(int i=0;i<n;i++)c[(a[q[i]]>>s)&1023]++;
        for(int i=1;i<1024;i++)c[i]+=c[i-1];
        for(int i=n-1;i>=0;i--)r[--c[(a[q[i]]>>s)&1023]]=q[i];
        swap(q,r);
    }
    d.init(n);int k=n;ans[k]=sum;
    for(int j=0;j<n;j++){
        int i=q[j],u=pos[i],x=d.find(u?p[u]:i),v=d.top[x];
        if(!v)continue;if(u)pos[v]=u;
        d.del(x,p[v]),sum-=a[i],ans[--k]=sum;
    }
    for(int i=1;i<=n;i++)cout<<(i<k?-1:ans[i])<<(i==n?'\n':' ');
}int main(){int T;for(cin>>T;T--;)solve();return 0;}