solution - P12017

littlebug · 2025-11-21 19:37:52 · 题解

你说得对，但是我的确注意力不够惊人。/ll

dp 显然，但是直接 dp 是不好做的，情况太多了，所以看看能不能找点限制，发现是可以的。

注意到如果连了一条边 u \to v，那么 v 可达的点 u 一定可达，且 v 不可到达 u，故必须满足 l_u > l_v；同理若连边 u \leftrightarrow v，那么必须满足 l_u = l_v。

有了这个性质之后，dp 需要考虑的情况就大大减少了。注意到 n \le 5000，所以应该是一个 O(n^2) 的 dp，考虑令 f_{u,i} 为「子树 u，u 可达的点数为 i」这个状态是否可达，转移考虑树上背包，直接分讨：

• 若 l_u = l_v，则此时有两种选择，连双向边或者不连边。

  • 若连双向边，那么 u,v 的可达点集（下面简称点集）一定是相同的，所以直接把两边的点集并起来即可：
  f_{u,i+j} \gets f_{u,i} \operatorname{and} f_{v,j}
  • 若不连边，则必须保证 f_{v,l_v} = 1。同时可以原封不动地转移：
  f_{u,i} \gets f_{u,i}

• 若 l_u > l_v，则只能连 u \to v 或不连边。

  • 若连 u \to v，那么就相当于把 u 的点集并上 v 的点集，但是不影响 v 的点集，于是就只能从 f_{v,l_v} 转移：
  f_{u,i+l_v} \gets f_{u,i} \operatorname{and} f_{v,l_v}
  • 若不连边，和 l_u = l_v 不连边的情况是一样的，在满足 f_{v,l_v} = 1 的前提下：
  f_{u,i} \gets f_{u,i}

• 若 l_u < l_v，则只能连 v \to u 或不连边。

  • 若连 v \to u，那么不会对 u 的点集产生任何影响，不过 u 关于其它点的选择会影响 v 的点集。而我们最后的目的需要让 u 合法，所以可以构造一种情况使得若 u 合法则 v 一定合法，也就是说 f_{v,l_v-l_u} 需要为 1。然后因为不会对 u 的点集产生影响所以转移还是原封不动：
  f_{u,i} \gets f_{u,i}

  同时这个构造也是充要的，因为如果没有方案能使得 u 合法，那么也没有必要考虑 v 是否合法了。

  • 若不连边，依然一样，在满足 f_{v,l_v} = 1 的前提下：
  f_{u,i} \gets f_{u,i}

直接转移即可，注意枚举范围为 sz_u 或 sz_v，就可以做到 O(n^2) 的总时间复杂度。

同时过程中需要注意，如果可以判断出不存在一种转移方案使得 v 合法，直接判为无解即可。

代码：

// === / 走吧 就算我们无法让大雨停下 还有我 陪你在雨里放肆奔跑啊 / ===

int n,a[N],sz[N];
vector <int> p[N];
bitset <N> f[N],g;

il bool dfs(int u,int ufa)
{
    sz[u]=1,f[u][1]=1;
    for(auto v:p[u]) if(v^ufa)
    {
        if(!dfs(v,u)) return 0;
        g=0;

        if(a[u]==a[v])
        {
            rep(i,0,sz[u]) rep(j,0,sz[v]) g[i+j]=g[i+j]|(f[u][i]&f[v][j]);
            if(f[v][a[v]]) rep(i,0,sz[u]) g[i]=g[i]|f[u][i];
        }

        else if(a[u]>a[v])
        {
            if(!f[v][a[v]]) return 0;
            rep(i,0,sz[u]) g[i+a[v]]=g[i+a[v]]|f[u][i];
            if(f[v][a[v]]) rep(i,0,sz[u]) g[i]=g[i]|f[u][i];
        }

        else
        {
            if(!f[v][a[v]]&&!f[v][a[v]-a[u]]) return 0;
            rep(i,0,sz[u]) g[i]=g[i]|f[u][i];
        }

        sz[u]+=sz[v],f[u]=g;
    }
    return 1;
}

il void solve()
{
    read(n),_::r(a,n),_::r(p,n-1,false);

    if(!dfs(1,0)) write((string)"NO");
    else write((string)(f[1][a[1]]?"YES":"NO"));
}

华风夏韵，洛水天依！