罓风猪会

tjx114514 · 2026-11-12 16:05:53 · 题解

这只猪会做但是没开，哭了。

将问题放到最大权独立集上考虑，记 f_{i,0/1} 表示选完 i 子树，i 选没选的最大值。

容易发现钦定权值只可能是正无穷或负无穷，也就是钦定一个点必选或不选。

记钦定的点为 s，则以 s 为根考虑问题。

若 f_{s,0}=f_{s,1}，钦定显然没有作用，答案为 0。

若 f_{s,0}>f_{s,1}，则钦定这个点必选。对儿子造成的影响是：删去 f_{v,1} 的转移。若 f_{s,0}<f_{s,1}，则钦定这个点不选。对儿子造成的影响是：增加一条 f_{v,1} 的转移。

考虑一个儿子 v，若 f_{v,0} ≥ f_{v,1}，则子树 v 不用做任何改变。否则证明这个钦定改变了子树 v 的选择，需要钦定 v 不选，然后继续处理 v 的子树。这其实缩减成了一个子问题。

所以可以 DP，设 g_x 表示决策完 x 子树后的对称差最小点数，则转移为 g_x=1+\sum_{v\in son} g_v[f_{v,0}<f_{v,1}]

注意到没有必要每次枚举根做 DP，直接换根即可做到 O(n)。

这里贴下代码：

#include<bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
const int N=1e6+5;
int T,n,a[N],f[N][2],g[N],ans;
vector<int> e[N];
void dfs(int x,int fa){
    g[x]=1;
    f[x][0]=0,f[x][1]=a[x];
    for(auto v:e[x]){
        if(v==fa) continue;
        dfs(v,x);
        g[x]+=(f[v][0]<f[v][1])*g[v];
        f[x][0]+=max(f[v][0],f[v][1]);
        f[x][1]+=f[v][0];
    }
    if(f[x][0]>f[x][1]) ans=max(ans,g[x]);
}
void dfs1(int x,int fa){
    if(f[x][0]>f[x][1]) ans=max(ans,g[x]);
    for(auto v:e[x]){
        if(v==fa) continue;
        int X0=f[x][0],X1=f[x][1],V0=f[v][0],V1=f[v][1],GX=g[x],GV=g[v];
        f[x][1]-=V0,f[x][0]-=max(V0,V1);
        g[x]-=(V0<V1)*GV;
        f[v][1]+=f[x][0],f[v][0]+=max(f[x][0],f[x][1]);
        g[v]+=(f[x][0]<f[x][1])*g[x];
        dfs1(v,x);
        f[x][0]=X0,f[x][1]=X1,f[v][0]=V0,f[v][1]=V1;
        g[x]=GX,g[v]=GV;
    }
}
void work(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],e[i].clear();
    ans=0;
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        e[u].pb(v),e[v].pb(u);
    }
    dfs(1,0);
    dfs1(1,0);
    cout<<ans<<'\n';
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    while(T--) work();
    return 0;
}

好了题解结束，谢谢观看。