题解：P17834 [CSP-S 2026] 研发基地

lailai0916 · 2026-10-31 18:22:09 · 题解

解题思路

二分半径 r。同时剥去 r 轮叶子，余树记为 C。若 |C|\le k，直接可行；否则，可将选点投影至 C 而不影响可行性。

核心叶子的最大悬挂深度为 r，故必须选取。漏选分叉点或留下两段缺口都会产生至少三个连通块，因此，只需在一条度为 2 的链上删去连续 D=|C|-k 个点。

将链编号为 0,\dots,s，两端保留。设 h_i 为点 i 的悬挂部分最大深度，b_i=r-h_i。删除 L+1,\dots,L+D 后，点 i 的悬挂部分无法被覆盖的条件为：

用差分维护这些禁用区间。扫描到 i 时检查 L=i-D\ge0：后续点 j>i 的区间左端点至少为 j-D>L，不会影响当前候选。若覆盖计数为 0，则找到合法缺口。D>2r 时无解。

预处理各点邻居剥叶时间的前三大值 t_1\ge t_2\ge t_3，不足补 0。该点为链内点的条件及其悬挂高度为：

沿前两大值对应的邻点扫描各链，每次判定 O(n)，总时间复杂度 O(n\log n)。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N=1000005;
vector<int> G[N];
int tim[N],deg[N],q[N],f[N],a[N],b[N],c[N],h[N];
bool mid[N];
bool check(int r,int n,int k)
{
    int len=deg[r+1]-k;
    if(len<=0)return 1;
    if(len>2*r)return 0;
    for(int i=1;i<=n;i++)mid[i]=h[i]>r&&c[i]<=r;
    for(int i=1;i<=n;i++)
    {
        if(!mid[i]||(mid[a[i]]&&mid[b[i]]))continue;
        int u=i,v=mid[a[i]]?b[i]:a[i],cur=0,j=0;
        f[0]=0;
        while(mid[u])
        {
            mid[u]=0;
            j++;
            f[j]=0;
            int d=r-c[u],l=max(0,j+d-len),p=j-d;
            if(l<p){f[l]++;f[p]--;}
            if(j>=len)
            {
                cur+=f[j-len];
                if(!cur)return 1;
            }
            int nxt=a[u]^b[u]^v;
            v=u;
            u=nxt;
        }
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int id,T;
    cin>>id>>T;
    while(T--)
    {
        int n,k;
        cin>>n>>k;
        for(int i=1;i<=n;i++)G[i].clear();
        for(int i=1;i<n;i++)
        {
            int u,v;
            cin>>u>>v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        int l=0,r=0;
        for(int i=1;i<=n;i++)
        {
            deg[i]=G[i].size();
            tim[i]=0;
            if(deg[i]==1){tim[i]=1;q[r++]=i;}
        }
        while(l<r)
        {
            int u=q[l++];
            for(auto v:G[u])
            {
                deg[v]--;
                if(deg[v]==1){tim[v]=tim[u]+1;q[r++]=v;}
            }
        }
        fill(deg,deg+n+2,0);
        for(int i=1;i<=n;i++)
        {
            deg[tim[i]]++;
            a[i]=b[i]=c[i]=0;
            for(auto v:G[i])
            {
                if(tim[v]>tim[a[i]])swap(v,a[i]);
                if(tim[v]>tim[b[i]])swap(v,b[i]);
                c[i]=max(c[i],tim[v]);
            }
            h[i]=tim[b[i]];
        }
        for(int i=n;i>=0;i--)deg[i]+=deg[i+1];
        l=0;
        r=n;
        while(l<r)
        {
            int mid=l+r>>1;
            if(check(mid,n,k))r=mid;
            else l=mid+1;
        }
        cout<<l<<'\n';
    }
    return 0;
}