NOIP2025 T3 题解

20_200 · 2025-12-03 17:28:51 · 题解

好题，比较能启发思维，来一篇启发式的题解。

如果遇到某一步想不到，可以先看看提示，然后再思考一段时间，再往下看。

::::warning[记号]{open}

$\text{path}(x,y)$ 表示 $x,y$ 的简单路径。 $|S|$ 表示集合 $S$ 的大小（元素个数）。注意此处约定根节点深度为 $1$，与题目中的定义不一致。因此，令 $m\gets m+1$。 :::: ::::info[一般性思考方向] 首先是最优化问题，然后观察数据范围发现大概率是 dp。发现直接写一个三次方暴力 dp 是容易的，但很难优化。所以这类题一般有这几种思路。 + 排除掉**一定不优**的情况，或者只考虑某些**一定不劣**的状态，减少需要表示的状态总量。 + 分析 dp 的**转移结构**，与排除掉的情况结合，根据这个结构的形态重新设计 dp。 + **合并多种本质相同的状态**成为一种状态。 + 在不等式同号的情况下，**弱化条件**。即允许一些不合法但是一定不优的情况存在，使得更弱的条件更容易维护，但同时不影响正确性。 :::: $O(\text{poly}(n))

跟正解没啥关系的 48 分暴力。 ::::warning[提示] 首先肯定不能直接把每个子树的权值集合放到状态里面，但 \text{mex} 的值本身可以。

那么考虑当某个子树的 \text{mex} 等于某个值时，它的里面可能有多少种情况？对该子树的上面有本质不同影响的又有多少？ :::: ::::info[算法 1] 是 f_{x,i,j} 表示当前考虑了 tr_x，且 x 的 \text{mex}=i，且 tr_x 内权值 >i 的数有 j 个的答案。

注意到 >i 的权值对该子树内任何一个点的 \text{mex} 都没有影响，所以不管这些 >i 的权值具体是什么，都可以算作一种状态。

转移类似树形背包状物，比较简单，不再赘述。

时间复杂度是 O(n^4) 的，因为需要两维树形背包。

第二维是 f'_{\max(i,j)}\gets f_{x,i}+f_{y,j} 形式的转移，这个可以用前缀 \text{max} 优化。加上这个就能做到 O(n^3) 。

由于和正解关系不大，这部分的代码没写。 :::: 一定不劣/不优的性质

以下性质的意义为，一定存在满足该性质的最优解。注意，是存在，不一定所有最优解都满足该性质。 ::::warning[提示] 考虑每个点填的数有没有大小顺序关系。 :::: ::::info[性质 1]

证明：$a_x=a_{p_x}$ 显然不优。而若 $a_x>a_{p_x}$，交换 $a_x,a_{p_x}$ 显然不劣。 :::: ::::warning[提示] 考虑每个点的权值是否有使自己的 $\text{mex}$ 变大。尝试按照这个方式把点分类并观察性质。对于每个没让自己的 $\text{mex}$ 变大的点，它们让谁变大了？ :::: ::::info[定义] 如果一个点的权值使得**自己的 $\text{mex}$ 变大**了（$+1$），则定义该点为 **A 类点**，否则为 **B 类点**。定义 $x$ **贡献到** $y$，当且仅当 $y$ 是 $path(x,1)$ 上满足 $\text{mex}$ 大于 $a_x$ 的**深度最大**的点。 :::: ::::info[性质 2] 可以发现，一个 B 类一定会贡献到一个 A 类点。因为如果 B 类点 $y$ 贡献到了 B 类点 $x$ 而 $x$ 贡献到了 $z$，那么把 $x$ 调整为 A 类点，或者让 $y$ 贡献到 $z$，这两者必有一个一定不劣。进一步发现，每个 B 类点一定贡献到它**到根的链上深度最大的 A 类点**。因为该 B 类点的权值小于该 A 类点的权值，不可能贡献到更上面。 :::: ::::warning[提示] 每个 A 类点在增大自己的 $\text{mex}$ 时，去除子树内最大的 $\text{mex}$ 并 $+1$，再加上贡献到它的 B 类点数量。如果把它弱化成，每个 A 类点可以任选一个子树里的 A 类点 $+1$ 再加上 B 类点的贡献作为自己的 $\text{mex}$，又会如何呢？ :::: ::::info[性质 3] 首先，若 A 类点 $x$ 选中了子树内的 A 类点 $y$ 作为转移到它的那个 $\text{mex}$，那么 $\text{path}(x,y)$ 上一定都是 A 类点，因为如果这条路径上有 B 类点，改成 A 类一定不劣。因此，**把每个 A 类点和它选中的子树里的 A 类点连接起来，形成了若干条链**。这些链两两不交，再加上所有的 B 类点，就构成了整棵树。 :::: **最优解的结构** ::::warning[提示] 整合一下刚才的 3 个性质。同时再分析一下 B 类点自己的 $\text{mex}$ 会是怎么得来的。 :::: ::::info[结构] B 类点的 $\text{mex}$ 一定是其子树内 A 类点的 $\text{mex}$ 的最大值。因此，依赖于同一个 A 类点的 B 类点也是一条链，不妨把它和那个 A 类点的链合并。那么，这个问题变成了，有若干条直链，两两交为空，整体并为全。每条链下面（深度大）是连续一段 A，上面（深度小）是连续一段 B。每个点对答案的贡献是它到根的链上深度最大的 A 类点**在该 A 类点所在的链中的深度**。 :::: $O(nm^2)

这个部分很接近正解，有 76pts。 ::::info[经典结论] 所有点的子树大小之和等于所有点深度之和，在这题里是 O(nm) 的。 :::: ::::warning[提示] 根据最优解结构重新设计 dp。因为链的长度不超过 m，考虑把链的长度加入 dp 状态。

转移的时候每个点都枚举子树是可以的。 :::: ::::info[算法 2] 设 f_{x,i},g_{x,i} 表示 x 是 A,B 类点且 x 到根的链上深度最大的 A 类点在其所在的链上的深度是 i 时，x 子树内的最大贡献和。

为了方便转移，设两个辅助数组 s_{x,i}=\sum\limits_{y\in son_x}g_{y,i},h_{x,y,i}=g_{x,i}+\sum\limits_{z\in \text{path}(x,y)}s_{z,i}-g_{z,i}，下文的式子会用到。

s$ 进行优化。 $f_{x,i}\gets i+s_{x,i}+\max(0,\max\limits_{y\in son_x}(f_{y,i+1}-g_{y,i}))

$g_{x,i}\gets\max(|tr_x|\times i,\max\limits_{y\in tr_x,d_y-d_x+1=i}i\times (i-1)+f_{y,i}+h_{x,y,i}-s_{y,i})

时间复杂度瓶颈在于 g 的转移。 :::: ::::success[76pts 代码]

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<ll,ll>
#define ve vector<ll>
#define fi first
#define se second
#define pb push_back
#define mid (l+r>>1)
#define lx (x<<1)
#define rx (x<<1|1)
using namespace std;
const ll N=8002,M=802;
ll T,n,m,d[N],p[N],dfn[N],dfm[N],dfp[N],f[N][M],g[N][M],h[N];
vector<ll>e[N];
ll&cmx(ll&x,ll y){return x=(x>y?x:y);}
void dfs(ll x){
    d[x]=d[p[x]]+1,dfp[dfn[x]=++n]=x;
    for(ll i:e[x])dfs(i);
    dfm[x]=n;
}
void Dfs(ll x){
    for(ll i:e[x])Dfs(i);
    for(ll i=1;i<=m;i++){
        ll s=i;
        for(ll y:e[x])s+=g[y][i];
        f[x][i]=s;
        for(ll y:e[x])
            cmx(f[x][i],s-g[y][i]+f[y][i+1]);
    }
    for(ll i=1;i<=m;i++){
        g[x][i]=(dfm[x]-dfn[x]+1)*i;
        for(ll j=dfn[x],y;j<=dfm[x];j++){
            y=dfp[j];
            h[y]=(x==y?0:h[p[y]]-g[y][i]);
            ll s=0;
            for(ll k:e[y])s+=g[k][i];
            h[y]+=s;
            if(d[y]-d[x]+1==i)
                cmx(g[x][i],h[y]-s+f[y][i]+i*(i-1));
        }
    }
}
void slv(){
    cin>>n>>m,m++;
    for(ll i=1;i<=n;i++)e[i].clear();
    for(ll i=2;i<=n;i++)cin>>p[i],e[p[i]].pb(i);
    n=0,dfs(1),Dfs(1);
    cout<<f[1][1]<<'\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--)slv();
    return 0;
}

::::

O(nm\log n)

这个部分是正解。 ::::warning[提示] 小常数带 \log 能过，尝试使用数据结构优化，最好用常数最小的树状数组。

考虑能不能做到每个子树只遍历一次。 :::: ::::info[算法 3] 把每次都会重新计算的 h_{x,y,i} 变为一个 h_{y,i}，一开始 h_{y,i}=i\times (i-1)+f_{y,i}，每次 x 变化的时候对它子树内的 h_{y,i} 进行修改。注意到 h 是一个祖先路径前缀和的形式，因此每一次 h 的变化都是子树加，即对于每个儿子 y 的子树内所有点，加上除了该儿子外其他儿子的 g。

且由于转移条件 d_y-d_x+1=i 使得所有 i 加在一起恰好把子树内每个点都遍历了一次，而所有子树大小之和是 O(nm) 的，因此可以直接遍历子树的所有点，每个点转移到对应的 i。

用树状数组维护子树加（dfn 序区间加）/单点查询即可做到 O(nm\log n)。 :::: ::::success[AC 代码]

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<ll,ll>
#define ve vector<ll>
#define fi first
#define se second
#define pb push_back
#define mid (l+r>>1)
#define lx (x<<1)
#define rx (x<<1|1)
using namespace std;
const ll N=8002,M=802;
ll T,n,m,d[N],p[N],dfn[N],dfm[N],dfp[N],f[N][M],g[N][M],h[N][M];
void add(ll x,ll k,ll y){
    for(;x<=n;x+=x&-x)h[x][k]+=y;
}
void mdf(ll l,ll r,ll k,ll y){
    add(l,k,y),add(r+1,k,-y);
}
ll qry(ll x,ll k,ll y=0){
    for(;x;x-=x&-x)y+=h[x][k];
    return y;
}
vector<ll>e[N];
ll&cmx(ll&x,ll y){return x=(x>y?x:y);}
void dfs(ll x){
    d[x]=d[p[x]]+1,dfp[dfn[x]=++n]=x;
    for(ll i:e[x])dfs(i);
    dfm[x]=n;
}
void Dfs(ll x){
    for(ll i:e[x])Dfs(i);
    for(ll i=1;i<=m;i++){
        ll s=0;
        for(ll y:e[x])s+=g[y][i];
        f[x][i]=s+i;
        for(ll y:e[x])
            cmx(f[x][i],s+i-g[y][i]+f[y][i+1]);
        g[x][i]=(dfm[x]-dfn[x]+1)*i;
        mdf(dfn[x],dfn[x],i,i*(i-1)+f[x][i]);
        for(ll y:e[x])
            mdf(dfn[y],dfm[y],i,s-g[y][i]);
    }
    for(ll j=dfn[x],k;j<=dfm[x];j++)
        k=d[dfp[j]]-d[x]+1,cmx(g[x][k],qry(j,k));
}
void slv(){
    cin>>n>>m,m++;
    for(ll i=1;i<=n;i++)
        e[i].clear(),fill(h[i],h[i]+m+1,0);
    for(ll i=2;i<=n;i++)cin>>p[i],e[p[i]].pb(i);
    n=0,dfs(1),Dfs(1);
    cout<<f[1][1]<<'\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--)slv();
    return 0;
}

::::

O(nm)

带 \log 做法已经可以通过，这部分只作为更优做法的讨论。代码懒得写了，只有口胡。

如果没有多测的话可以加强到 n\le 10^5。 ::::warning[提示] 带 \log 做法的瓶颈在于每次遍历子树需要对每个点都做一次树状数组上的查询，遍历的总点数是 O(nm) 的，因此需要的 O(nm\log n) 的复杂度。

但是真的有必要遍历整个子树吗？能不能把不同的点再压缩一下呢？ :::: ::::info[算法 4] 其实转移只和深度有关（只有唯一的限制 d_y-d_x+1=i），所以可以把每个子树内每种相对深度的点合并起来留下一个最大值。

深度有关的 dp 经典方法就是长链剖分优化，不会的左转 P4292。

修改操作，对每个轻儿子的子树加，直接暴力枚举所有有效的深度一个一个加就可以了。

对于重儿子的子树加，不能直接枚举不然复杂度会炸，但是可以打标记，这样 O(1) 就能完成。然后把轻儿子合并上来的时候，以及这条链到顶了，作为轻儿子被合并的时候，都加上这个标记再做其他操作即可。

根据长链剖分的复杂度原理，即每条长链都只会在自己的顶端的点作为轻儿子被合并一次，所以复杂度是 O(nm) 的。 ::::

其实这场 NOIP 题还是很好的，这题也算是那种思路高妙，代码清新，做起来特别爽的类型，适合放 NOI D1T2。

但正赛出 NOIPlus 过于搞人心态，sale 调不出来直接 AFO 了，崩溃。