好题！

题解 #

答案分两步 dfs，第一个 dfs 用来计算 $sub_i$ ： $i$ 的子树中的的子图的最大差值。稍微有点绕，其实题目中的“子树”应该叫子图比较合适，因为是无根树，说子图没什么意义。但我们 dfs 的时候其实是把图当成有根树，所以第一次 dfs 得到的答案只考虑了子树的贡献，剩余部分的贡献由第二个 dfs 算。其他部分的贡献看英文吧……懒得再写一遍了（逃）。

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
 
using namespace std;
typedef long long ll;
 
const int N=2e5+5;
vector<int> G[N];
int ans[N],a[N],dp[N];
void dfs1(int u,int fa){
	dp[u]=a[u];
	for(auto it:G[u]){
		if(it!=fa){
			dfs1(it,u);
			dp[u]+=max(0,dp[it]);
		}
	}
}
void dfs2(int u,int fa,int pd){
	ans[u]=dp[u]+pd;
	for(auto v:G[u]){
		if(v!=fa){
			dfs2(v,u,max(ans[u]-max(dp[v],0),0));
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for1(i,n) {
		cin>>a[i];
		if(!a[i]) a[i]=-1;
	}
	forn(i,n-1){
		int x,y;
		cin>>x>>y;
		G[x].pb(y);
		G[y].pb(x);
	}
	dfs1(1,-1);
	dfs2(1,-1,0);
	for1(i,n) cout<<ans[i]<<' ';
	return 0;
}

CodeForces 1324F - Maximum White Subtree 题解

题解 #

Code #