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

· · 题解

题意

给定一个无根树 T，节点 i 有权值 v_i，你需要修改恰好一个节点的权值，得到一颗新的树 T_1。设编号集合 S 满足 S 中的节点在 T 上互不相邻且权值和最大化，S_1 满足 S_1 中的节点在 T_1 上互不相邻且权值的最大化。再定义 S 和 S_1 的差异值为恰好在 S 和 S_1 之一中出现的节点编号个数。你要使得修改后 S 和 S_1 的最小差异值最大。

思路

首先先考虑一种 O \left ( n^2 \right ) 的做法，枚举那个修改权值的节点然后 O \left ( n \right ) 求出 S 和 S_1 的最小差异值的最大值。

设当前枚举到了修改第 m 个节点的权值。设 f_{i,0} 为不选节点 i 的情况下能得到的最大权值和，f_{i,1} 为在选当前节点的情况下能得到的最大权值和。则：

f_{m,0}=\sum_{k} \max \left ( f_{k,0},f_{k,1} \right ) f_{m,1}=v_m + \sum_{k} f_{k,0}

那么可以发现，当把 v_m 改成极大值时 S_1 必然为 f_{m,0} 里的方案，当把 v_m 改成极小值的时候 S_1 必然为 f_{m,1} 里的方案。

这时可以分讨 3 种情况：

那么对于前两种情况，就只需要求出 f_{m,0} 里的方案和 f_{m,1} 里的方案的差异值的最小值即可。这个其实也可以树形 dp 的，设 g_m 为 f_{m,0} 和 f_{m,1} 的差异值的最小值。那么转移方程为，

g_m=1 + \sum_{k} \left [ f_{k,0} < f_{k,1} \right ] g_k

这样就得到了 O \left ( n^2 \right ) 的写法。这时可以发现，对于每个点 m \left ( 1 \le m \le n \right ) 可以用换根 dp 来快速求出以它为根时其 f_{m,0},f_{m,1} 和 g_m 的值，这样子就有了 O \left ( n \right ) 的写法。

代码

#include<bits/stdc++.h>
using namespace std;
long long t,n,l,r,ma,a[1000010],f[1000010][2],g[1000010];
vector<long long> v[1000010];
void dfs(long long m,long long fa){
    f[m][0]=0,f[m][1]=a[m],g[m]=1;
    for(int i=0;i<v[m].size( );i++){
        if(v[m][i]==fa) continue;
        dfs(v[m][i],m);
        f[m][1]+=f[v[m][i]][0];
        f[m][0]+=max(f[v[m][i]][0],f[v[m][i]][1]);
        if(f[v[m][i]][1]>f[v[m][i]][0]){
            g[m]+=g[v[m][i]];
        }
    }
    return;
}
void dfs2(long long m,long long fa,long long ff0,long long ff1,long long gg){
    f[m][0]+=max(ff0,ff1);
    f[m][1]+=ff0;
    if(ff0<ff1) g[m]+=gg;
    if(f[m][0]!=f[m][1]) ma=max(ma,g[m]);
    for(int i=0;i<v[m].size( );i++){
        if(v[m][i]==fa) continue;
        dfs2(v[m][i],m,f[m][0]-max(f[v[m][i]][0],f[v[m][i]][1]),f[m][1]-f[v[m][i]][0],g[m]-(f[v[m][i]][1]>f[v[m][i]][0])*g[v[m][i]]);
    }
    return;
}
int main(  ){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        for(int i=1;i<n;i++){
            cin>>l>>r;
            v[l].push_back(r);
            v[r].push_back(l);
        }
        ma=0;
        dfs(1,0);
        dfs2(1,0,0,0,0);
        cout<<ma<<"\n";
        for(int i=1;i<=n;i++){
            v[i].clear( );
        }
    }
    return 0;
}