题解：P12017 [NOISG 2025 Finals] 可达性

· · 题解

P12017 [NOISG 2025 Finals] Reachability

Algorithm:

树形背包。

Solution:

被薄纱了。

看到这道题让我会想到了省选的岁月，但其实两道题目并没有任何相似之处。

观察到 u \rightarrow v 的边相当于让 u 能够到达的点加上 v 能够到的点的数量。这能够让我们发现两点之间可能的边的限制。具体而言如下所示：

  1. 当 l_u=l_v 时，u,v 之间的边要么为双向边或者没有连边，原因是若为单向边则两个点能够到达点的数量至少差 1。
  2. 当 l_u \neq l_v 是，u,v 之间的便要么为单向边（l 值大的点连向 l 值小的点）或者没有连边。

加上之前的观察，不难发现是一个树上背包的形式。所以考虑设 f_{u,i} 代表在计算到 u 的时候，u 能够到达的点数量为 i 是否合法。转移只要按照上面的分类讨论一下即可，具体而言如下所示：（siz_i 为 i 这个点的子树大小）

  1. 当 l_u=l_v 时：
  2. 当 l_u > l_v 时：
  3. 当 l_u<l_v 时：

不满足的情况可以直接输出 NO 退出。最后检查根节点是否合法即可。在实际实现的过程中会遇到 f_{u,i} 在一个儿子被更新后去更新其他状态，所以需要辅助数组 g_i 用来暂时存储 f_{u,i} 的状态，更新完后重新赋值。

Code:

namespace Mr_Az{
    const int N=5008;
    int T=1;
    int n;
    int l[N],siz[N];
    bool f[N][2*N],g[2*N];
    vector<int> e[N];
    void dfs(int u,int fa){
        siz[u]=1;
        for(auto v:e[u]){
            if(v==fa) continue;
            dfs(v,u);
            if(l[u]==l[v]){// 所达城市数量一致
                // 1. 连边
                for(rint i=0;i<=siz[u];i++)
                    for(rint j=0;j<=siz[v];j++)
                        g[i+j]|=(f[u][i]&f[v][j]);

                // 2. 断开(下面必须要满足要求)
                if(f[v][l[v]]){
                    for(rint i=0;i<=siz[u];i++) g[i]|=f[u][i];
                }
            }
            else{// 所达城市数量不一致
                if(l[u]>l[v]){// 1. u->v 或不连边
                    if(!f[v][l[v]]){puts("NO");exit(0);}
                    else{
                        for(rint i=0;i<=siz[u];i++){
                            g[i+l[v]]|=f[u][i];
                            g[i]|=f[u][i];
                        }
                    }
                }
                else{// 2. v->u 或不连边
                    if(!f[v][l[v]]&&!f[v][l[v]-l[u]]){puts("NO");exit(0);}
                    for(rint i=0;i<=siz[u];i++) g[i]|=f[u][i];
                }               
            }
            siz[u]+=siz[v];
            for(rint i=0;i<=siz[u];i++) f[u][i]=g[i];
            mem(g,0);
        }
    }
    inline void solve(){
        read(n);
        for(rint i=1;i<=n;i++) read(l[i]);
        for(rint i=1,u,v;i<n;i++){
            read(u,v);
            e[u].pb(v);e[v].pb(u);
        }
        for(rint i=1;i<=n;i++) f[i][1]=1;
        dfs(1,0);
        if(f[1][l[1]]) puts("YES");
        else puts("NO");
    }
    inline void mian(){if(!T) read(T);while(T--) solve();}
}