P11887 「Stoi2025」爱在西元前

Genius_Star · 2026-11-12 14:44:51 · 题解

简单题，场切了。

思路：

考虑调整一位的权值本质是在干什么？显然可以看出是在使得后手是否必选某个点或者一定不选某个点。

具体的，设 f_{u, 0/1} 表示全局情况下是否选 u 的最大独立集权值，分讨一下：

• 若 f_{u, 0} > f_{u, 1}，则在 T 中必选 f_{u, 0} 的某个方案；在我们修改后，可以将 u 的权值改到 +\infty 那么此时后手就必须选 f_{u, 1} 的方案了。

• 若 f_{u, 1} > f_{u, 0}，则在 T 中必选 f_{u, 1} 的某个方案；于是可以将 u 的权值改为 -\infty 此时后手就必选 f_{u, 0} 的方案了。

• 否则 f_{u, 0} = f_{u, 1}，你发现无论怎么改后手都可以取和先手一样的，于是不可能造成贡献。

所以当 f_{u, 0} \ne f_{u, 1} 时，你可以通过修改使得一个选择 f_{u, 0} 的方案一个选择 f_{u, 1} 的方案，于是可以转化为使得 |F_{u, 0} \oplus F_{u, 1}| 尽可能小的问题了，最后对每个 u 的答案取 \max。

显然可以继续 dp，设 g_u 表示 |F_{u, 0} \oplus F_{u, 1}| 最小是多少，因为：

于是当 f_{v, 0} < f_{v, 1} 时 f_{u, 0} 必须要选择 f_{v, 1} 会和 f_{u, 1} 选的 f_{v, 0} 造成 g_v 的贡献，否则一定全部选 f_{v, 0} 不造成贡献，于是：

直接暴力是 O(n^2) 的，无法通过；优化是容易的，直接换根 dp 即可。

时间复杂度为 O(n)。

完整代码：

#include<bits/stdc++.h>
#define fi first

#define se second

#define lowbit(x) ((x) & (-(x)))

using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
int T, n, mx;
int a[N], g[N];
ll f[N][2];
vector<int> E[N];
inline void add(int u, int v){
    E[u].push_back(v);
    E[v].push_back(u);
}
inline void dfs(int u, int fa){
    f[u][0] = 0, f[u][1] = a[u];
    g[u] = 1;
    for(auto v : E[u]){
        if(v == fa)
          continue;
        dfs(v, u);
        if(f[v][0] < f[v][1])
          g[u] += g[v];
        f[u][0] = f[u][0] + max(f[v][0], f[v][1]);
        f[u][1] += f[v][0];
    }
}
inline void dfs2(int u, int fa){
    // cerr << u << ' ' << f[u][0] << ' ' << f[u][1] << ' ' << g[u] << '\n';
    if(f[u][0] != f[u][1])
      mx = max(mx, g[u]);
    // reverse(E[u].begin(), E[u].end());
    for(auto v : E[u]){
        if(v == fa)
          continue;
        ll fu0 = f[u][0] - max(f[v][0], f[v][1]);
        ll fu1 = f[u][1] - f[v][0];
        int gu = g[u] - ((f[v][0] < f[v][1]) ? g[v] : 0);
        ll pf0 = f[v][0], pf1 = f[v][1], pg = g[v];
        f[v][0] += max(fu0, fu1);
        f[v][1] += fu0;
        if(fu0 < fu1)
          g[v] += gu;
        // if(v == 8)
        //   cerr << g[u] << ' ' << gu << '';
        // if(v == 8)
        //   exit(0);
        dfs2(v, u);
        f[v][0] = pf0, f[v][1] = pf1, g[v] = pg;
    }
}
inline void solve(){
    mx = 0;
    n = read();
    for(int i = 1; i <= n; ++i){
        a[i] = read();
        E[i].clear();
    }
    for(int u, v, i = 1; i < n; ++i){
        u = read(), v = read();
        add(u, v);
    }
    dfs(1, 0);
    dfs2(1, 0);
    // for(int u = 1; u <= n; ++u){
    //     dfs(u, 0);
    //     // cerr << u << ' ' << f[u][0] << ' ' << f[u][1] << ' ' << g[u] << '\n';
    //     // cerr << g[9] << '\n';
    //     if(f[u][0] == f[u][1])
    //       continue;
    //     mx = max(mx, g[u]);
    // }
    write(mx);
    putchar('\n');
}
int main(){
    T = read();
    while(T--)
      solve();
    return 0;
}