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

· · 题解

这题有点难度。

读完题发现我们似乎束手无策。因为情况很多。

我们观察一下，树上两个点 u，v 的连边的情况。 对于情况 1，我们发现 u 到达的点，v 一定能到达，而 v 到达的点 u 不一定到达。所以 l_u < l_v 。对于情况 2 也是同理的。

对于情况 3（双向），我们发现两个点位于同一个连通块中，所以 l_u=l_v。

对于情况 4（无），我们发现它们两个的到达点的数量没有必然联系。

这时我们就可以考虑对树上两个点讨论。

考虑 f_{u,i} 表示以 u 为根,到达的点的数量为 i 个是否可行，所以转移操作均为位操作。

我们对两个点的到达点数量讨论。

第一种情况：若 l_u=l_v，要么情况 3，要么情况 4。

情况 3 就有如下状态转移：

f_{u,i+j} \gets f_{u,i+j} \ |\ (f_{u,i}\ \&\ f_{v,j})

相当于把两个连通块合并。

对于情况 4，由于 u，v 是断开的，那么要想 u 满足，必然前提 v 要满足,即 f_{v,l_v}=1。

此时 u 就直接继承。

f_{u,i}\gets f_{u,i}

值得说明的是，以上方程的后面的 f_{u,i} 是指之前的 f_{u,i} 。

第二种情况：若 l_u>l_v，要么情况 2，要么情况 4。

对于情况 2，那么 v 能到达的 u 就可以到达了，而对于 v 就没有影响，那么前提就是 f_{v,l_v}=1。

此时：

f_{u,i+l_v} \gets f_{u,i+l_v} \ |\ (f_{u,i}\ \&\ f_{v,l_v})

情况 4 与第一种情况相同，这里不再赘述。

第三种情况：若 l_u<l_v，要么情况 1，要么情况 4。

对于情况 1，那么 u 能到达的 v 就可以到达了，而对于 u 就没有影响，我们要使其连接后合法，那么就必须 f_{v,l_v-l_u}=1。

由于对 u 没有影响所以直接继承：

f_{u,i}\gets f_{u,i}

情况 4 不再赘述。

我们使用类似滚动数组的方法搞个数组 g 暂存一下答案。防止更新答案把之前的答案污染。然后在将其赋值回 f。

::::success[AC code:]

#include<bits/stdc++.h>
using namespace std;
const int N = 5e3+5;
int n, g[N], l[N], sz[N], f[N][2 * N];
vector<int> e[N];
inline void dfs(int u, int fa) {
    sz[u] = 1;
    for (int v : e[u]) {
        if (v == fa)
            continue;
        dfs(v, u);
        if (l[u] == l[v]) {
            for (int i = 0; i <= sz[u]; i++)
                for (int j = 0; j <= sz[v]; j++)
                    g[i + j] |= (f[u][i] & f[v][j]);
            if (f[v][l[v]])
                for (int i = 0; i <= sz[u]; i++)
                    g[i] |= f[u][i];
        }
        else {
            if (l[u] > l[v]) {
                if (!f[v][l[v]]) {
                    puts("NO");
                    exit(0);
                }
                for (int i = 0; i <= sz[u]; i++) {
                    g[i + l[v]] |= f[u][i];
                    g[i] |= f[u][i];
                }
            }
            else {
                if (!f[v][l[v]] && !f[v][l[v] - l[u]]) {
                    puts("NO");
                    exit(0);
                }
                else {
                    for (int i = 0; i <= sz[u]; i++)
                        g[i] |= f[u][i];
                }
            }
        }
        sz[u] += sz[v];
        for (int i = 0; i <= sz[u]; i++)
            f[u][i] = g[i], g[i] = 0;
    }
}
int main() {
    ios::sync_with_stdio(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);
    }
    for (int i = 1; i <= n; i++)
        f[i][1] = 1;
    dfs(1, 0);
    puts(f[1][l[1]] ? "YES" : "NO");
    return 0;
}

::::