题解：AT_arc157_e [ARC157E] XXYX Binary Tree

LastKismet · 2025-08-19 22:17:07 · 题解

Sol

本题的关键即为 Y 点。

不难发现由题中限制，所有 Y 点必然为独立集，且 Y 点的数量是一定的。

具体地，若根节点为 Y，则叶子节点 Y 的数量为 B+1-\frac{C}{2}；否则，为 B-\frac{C}{2}。同时非叶子节点 Y 的数量为 \frac{C}{2}。

那么我们可以这么树上 DP，记 f_{x,i=0/1,j,k} 表示以 x 为根子树中，x 是或不是 Y，存在 j 个叶子节点为 Y 和 k 个非叶子节点为 y 是否可行。

考虑优化，我们记 f_{x,i=0/1,j} 表示以 x 为根子树中，x 是或不是 Y，存在 j 个叶子节点为 Y 时最多的非叶子节点为 Y 的个数，显然最后要求非叶子 Y 节点数量不超过最多值即可。复杂度由树上背包可证为 O(n^2)。

Code

const int N=1e4+5;

int n,a,b,c;
vec<int> g[N];
int f[N][2][N>>1];
int sz[N];

inline void dfs(int x=1){
    if(g[x].empty()){
        sz[x]=1;
        f[x][0][0]=0,f[x][1][1]=0;
        f[x][0][1]=f[x][1][0]=-inf;
        return;
    }
    sz[x]=0;
    f[x][1][0]=1;f[x][0][0]=0;
    for(auto y:g[x]){
        dfs(y);
        rep(i,sz[x]+1,sz[x]+sz[y])f[x][0][i]=f[x][1][i]=-inf;
        per(i,sz[x],0)per(j,sz[y],0)chmax(f[x][0][i+j],f[x][0][i]+max(f[y][0][j],f[y][1][j])),chmax(f[x][1][i+j],f[x][1][i]+f[y][0][j]);
        sz[x]+=sz[y];
    }
}

inline void Main(){
    cin>>n>>a>>b>>c;
    if(n==1)return put("Yes"),void();
    rep(i,1,n)g[i].clear();
    rep(i,2,n){
        int p;cin>>p;
        g[p].pub(i);
    }
    if(c&1)return put("No"),void();
    dfs();
    if(sz[1]>=b-c/2&&b>=c/2&&f[1][0][b-c/2]>=c/2||sz[1]>=b+1-c/2&&b+1>=c/2&&f[1][1][b+1-c/2]>=c/2)put("Yes");
    else put("No");
}