题解：P11887 「Stoi2025」爱在西元前

DSD486 · 2026-11-12 19:59:39 · 题解

简单换根 dp，感觉到不了紫。

容易发现操作本质钦定一个点必选或必不选。

我们先枚举点 p 作为根，同时表示操作它。

此时可以在树上用 dp 求最大独立集。

状态即为 f_{i , 0/1} 表示 i 不选或选。

• 若 f_{p , 0} = f_{p , 1} 则当前点没必要被操作。

• 若 f_{p , 0} > f_{p , 1}，则钦定当前点必选，使差值尽可能大。

• 若 f_{p , 0} < f_{p , 1} 同理钦定当前点必不选。

那如何求出前后最大独立集的差值？

再用一个 dp，g_u 表示 u 被改变决策（比如从必选改为必不选）子树内前后最大独立集的最小差值。

初值自然为 1。

同样分讨，转移。

设 v 是 u 的子节点。

• 若 f_{v , 0} = f_{v , 1} 则当前点没必要被改变。

• 若 f_{v , 0} > f_{v , 1}，当前点本来就必不选，此时也不会被改变。因为 v 不被改变，子树内节点也没必要改变，所以提供 0 的贡献。

• 若 f_{v , 0} < f_{v , 1}，当前点会被改变，提供 g_v 的贡献。

此时时间复杂度 \mathcal{O}(n ^ 2)。

简单换根复杂度 \mathcal{O}(n)。

::::success[Code]

#include <bits/stdc++.h>
#define int long long
#define PII pair < int , int >
#define x first
#define y second
using namespace std ; 
bool bbb ; 

const int N = 1e6 + 5 ; 
int n , c[N] , ans ; 
vector < int > mp[N] ; 
int f[N][2] , g[N] ; 
void dfs(int u , int fa){
    f[u][0] = 0 , f[u][1] = c[u] ; 
    g[u] = 1 ; 
    for(int v : mp[u]) if(v != fa){
        dfs(v , u) ; 
        f[u][1] += f[v][0] , 
        f[u][0] += max(f[v][0] , f[v][1]) ; 
        if(f[v][1] > f[v][0])
            g[u] += g[v] ; 
    }
}
void dfs2(int u , int fa , int f0 , int f1 , int gg){
    int t0 = f[u][0] + max(f0 , f1) , t1 = f[u][1] + f0 , gu = g[u] + (f1 > f0) * gg ; 
    if(t0 != t1) ans = max(ans , gu) ; 
    for(int v : mp[u]) if(v != fa)
        dfs2(v , u , t0 - max(f[v][0] , f[v][1]) , t1 - f[v][0] , gu - (f[v][1] > f[v][0]) * g[v]) ; 
}

void solve(){
    cin >> n ; 
    for(int i = 1 ; i <= n ; i++) cin >> c[i] ; 
    for(int i = 1 , u , v ; i < n ; i++){
        cin >> u >> v ; 
        mp[u].push_back(v) , 
        mp[v].push_back(u) ; 
    }
    ans = 0 ; 
    dfs(1 , 0) , dfs2(1 , 0 , 0 , 0 , 0) ; 
    cout << ans << '\n' ; 
    for(int i = 1 ; i <= n ; i++) mp[i].clear() ; 
}

bool eee ; 
signed main(){
//  freopen("night.in" , "r" , stdin) ; 
//  freopen("night.out" , "w" , stdout) ; 
    ios :: sync_with_stdio(0) ; 
    cin.tie(0) ; cout.tie(0) ; 
    cerr << "Memory: " << abs((char*)&eee - (char*)&bbb) / 1024.0 / 1024.0 << " MB\n" ; 
    int T ; cin >> T ; 
    while(T--) solve() ; 
    return 0 ; 
}
/*


2
10
3 2 7 -2 4 -1 10 0 5 1
1 7
2 3
3 7
3 4
5 6
5 7
7 9
8 10
9 10
4
1 2 3 4
1 4
2 4
3 4


*/

::::