【动态规划】P12017 [NOISG 2025 Finals] 可达性

LeftChild · 2026-08-09 19:34:10 · 题解

对于一个点 x 和它的一个邻居 y，若它们之间的边没有被“关闭”，考虑以下比较显然的结论：

采用树形 DP，记 f_{i,j} 表示点 i 向它的子树内可以到达点的数量为 j 是否可行。设当前考虑非叶子结点 u 作为父亲结点，点 v 为儿子结点，为避免处理时数据被覆盖，因此记 f'_{u,j}。 表示在处理这个儿子前的情况。

分类讨论（注：\lor 表示逻辑或）：

• 两点之间无边：若 f_{v,l_v} 即不连边满足 v 的限制，那么有 f_{u,i} \leftarrow f_{u_i} \lor f'_{u,i}。
• 两点之间有边
  • 若 l_u=l_v：两点之间有双向边：当 f_{v,j} 为真时，有 f_{u,i+j} \leftarrow f_{u,i+j} \lor f'_{u,i}。
  • 若 l_u>l_v：从 u 向 v 连边：f_{u,i+l_v}\leftarrow f_{u,i+l_v} \lor f'_{u,i}。
  • 若 l_u<l_v，尝试从 v 向 u 连边：
  • 若 f_{v,l_v-l_x} 为真，则 f_{u,i} \leftarrow f_{u,i} \lor f'_{u,i}。
  • 否则不能从 v 向 u 连边。此时如果第一种情况 f_{v,l_v} 也不成立，说明此处不能连边也不能断边，则无解。

如果不存在上述矛盾情形且根节点能满足 f_{1,l_1}为真的条件，则有解。

:::success[AC 代码]

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5005;
int n, l[maxn], sz[maxn];
bool dp[maxn][maxn], f[maxn];
bool flag = true;
vector<int> e[maxn];
void dfs(int x, int fa)
{
    sz[x] = 1;
    dp[x][1] = true;
    for (int v : e[x])
    {
        if (v == fa)
            continue;
        dfs(v, x);
        for (int i = 0; i <= n; i++)
        {
            f[i] = dp[x][i];
            dp[x][i] = 0;
        }
        if (dp[v][l[v]])
        {
            for (int i = 0; i <= sz[x]; i++)
                dp[x][i] |= f[i];
        }
        if (l[x] == l[v])
        {
            for (int i = 0; i <= sz[x]; i++)
                for (int j = 0; j <= sz[v]; j++)
                    dp[x][i + j] |= f[i] & dp[v][j];
        }
        else if (l[x] > l[v])
        {
            for (int i = 0; i <= sz[x]; i++)
                dp[x][i + l[v]] |= f[i];
        }
        else if (!dp[v][l[v]] && !dp[v][l[v] - l[x]])
            flag = false;
        else if (!dp[v][l[v]])
        {
            for (int i = 0; i <= sz[x]; i++)
                dp[x][i] |= f[i];
        }
        sz[x] += sz[v];
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> l[i];
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0);
    if (!flag || !dp[1][l[1]])
        cout << "NO\n";
    else
        cout << "YES\n";
    return 0;
}

代码经过了格式化。 :::