CF1610H Squid Game 题解

贪心/树形DP

Statement

CF1610H Squid Game - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

给定?个 \(n\) 个点的树，以及 \(m\) 条链。你需要选取尽可能少的点，使得对于每?条链 \((x_i,y_i)\)，都存在?个被选的 \(z\) 点 ，使得链上到 \(z\) 距离最短的点既不是 \(x_i\) 也不是 \(y_i\)

\(n,m\le 3\times 10^5\)

Solution

这里主要介绍 DP 的方法。（idea 不是我的）

贪心的想法大致是对于曲链而言，需要选择一个点在链两端的某个共同祖先

对于一条直链而言，我们显然需要选到链上某个点，同时，我们可以贪心地把选择的这个点尽可能往上靠，这样可能可以顺便处理掉曲链

同时，可能出现两条直链重叠的情况，所以我们处理的时候需要按 dfs 序来

最后，如果处理完直链之后还有曲链不满足，直接选根节点即可

DP 方法与贪心想法有一定联系，设 \(dp_u\) 表示处理完所有完全包含在 \(u\) 子树中的直链需要选的最少点数

所谓完全包含，就是两个端点都在 \(u\) 子树中，考虑转移，显然有

然后，直接给出另外一种转移：对于一条直链 \((u\to w\leadsto v)\) , \(\to\) 表示通过一条边到达， \(\leadsto\) 表示通过一坨边到达，有

容易理解嘛，按照上面贪心的思路，我们为了处理这条以 \(u\) 为起点的直链，应该选择 \(w\) 点

思考发现，不会存在多条重叠直链导致 DP 错误的情况

最后来处理曲链，对于一条曲链 \(u\leadsto v\) ，\(ans=max(ans,dp_u+dp_v+1)\)

思考发现，不会存在需要选则根节点时，因为 \(dp_u+dp_v+1\) 太小导致没有选中根节点的情况

Code

#include
#define pii pair
using namespace std;
const int N = 3e5+5;

char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int read(){;
    int s=0,w=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
    return s*w;
}

int dep[N],f[N][22],dp[N];
vectorEdge[N],line[N];
vectorarc;
int n,m,ans;

void dfs(int u){
    for(int i=1;i<=20;++i)f[u][i]=f[f[u][i-1]][i-1];
    for(auto v:Edge[u])dep[v]=dep[f[v][0]=u]+1,dfs(v);
}
int jump(int u,int v){
    for(int i=20;~i;--i)
        if(dep[f[u][i]]>dep[v])u=f[u][i];
    return u;
}
void DP(int u){
    for(auto v:Edge[u])DP(v),dp[u]+=dp[v];
    for(auto v:line[u])dp[u]=max(dp[u],dp[v]+1);
}

signed main(){
    n=read(),m=read();
    for(int i=2,x;i<=n;++i)
        x=read(),Edge[x].push_back(i);
    dfs(dep[1]=1);
    for(int i=1,u,v;i<=m;++i){
        u=read(),v=read();
        if(dep[u]