题解：CF627D Preorder Test

masterhuang · 2025-10-27 21:46:55 · 题解

依然是保留的批判所有题解环节。感觉讲得太烂，甚至有一篇假了。

首先二分，\ge mid 设为 1，否则设为 0。

转化为可以任意选根，任意钦定 dfs 序。要求找到最长的 dfs 序全 1 前缀。判断是否 \ge k。

考虑 dfs 序前缀的本质是什么。

相当于把起点 S 到 dfs 前缀最后一个点 T 这条路径拎出来，摊平。

那么对于这条链上的所有子树，要么全选要么全不选。

考虑类似求直径那样设计 dp，直径对应现在 S\to T 这条链。

记 f_u 表示 u 子树内延伸下去一条链，此时最多能选多少个点。

转移枚举若干全选加上一个继续延伸下去，定义 S=\{v: f_v\neq sz_v\}，则：

然后贡献到 ans 就再贡献一个 S 中 f 值的次大值即可，即从 u 开始往下引两条链贡献给答案。

但是这样有些问题，我们没有考虑根向子树。

难道要换根 dp 嘛？并不是。

考虑 dfs 中 dp 的时候，初始让 a_x 权值最小的点 x 为根。

则在 mid>a_x 的时候，根向子树 一定不能被全选，dp 过程正确。当 mid=a_x 的时候显然也正确。

于是通过简单的 钦定根 就修正了这个漏洞。

dp 维护最大值次大值，总复杂度 \mathcal{O}(n\log a_i) 或 \mathcal{O}(n\log n)，取决于二分细节，差别不大。

:::info[代码]

#include<bits/stdc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=2e5+5;
int n,m,k,rt,a[N],mx,s[N],sz[N];
basic_string<int>E[N];
void dfs(int x,int F)
{
    s[x]=sz[x]=1;int X=0,Y=0;
    for(int y:E[x]) if(y^F)
    {
        dfs(y,x),sz[x]+=sz[y];
        if(s[y]==sz[y]) s[x]+=s[y];
        else
        {
            if(s[y]>=X) Y=X,X=s[y];
            else Y=max(Y,s[y]);// 维护最大次大
        }
    }
    (a[x]>=m)?mx=max(mx,(s[x]+=X)+Y):s[x]=0;
  // 更新答案
}
inline bool chk(){mx=0;dfs(rt,0);return mx>=k;}
int main()
{
    cin.tie(0)->sync_with_stdio(0);cin>>n>>k;
    int l=1e9,r=0,ans;
    for(int i=1;i<=n;i++) cin>>a[i],l=min(l,a[i]),r=max(r,a[i]);
    for(int i=1,u,v;i<n;i++) cin>>u>>v,E[u]+=v,E[v]+=u;
    rt=min_element(a+1,a+1+n)-a;// 二分
    while(l<=r) m=(l+r)>>1,chk()?ans=m,l=m+1:r=m-1;
    return cout<<ans,0;
}

:::