题意
给你无根一颗树，每个节点是黑色或白色。对于每一个节点，问包含该节点的权值最大的子树。
子树的权值等于子树中白点的个数减去黑点的个数。
注意，这里的子树指的是树的联通子图。
解题思路
这场就这题卡的比较久。
首先，如果是有根树的话，只需要dfs一遍就能得出根的答案。
设根为1，将无根树转为有根树。对于每一个节点定义(ans)和(val)。
其中，(val_u=sum_{val_v>0且v是u的儿子}{val_v})
然后，再一次dfs就可以获得所有节点的答案。
对于节点(u)和他的父节点(f)，他往子节点方向的结果已经确定了，就是(val_u)，现在就剩他往(f)方向的结果需要计算。如果(val_u>0)，那么往(f)方向的权值就是(ans_f-val_u)，否则就是(ans_f)。如果往(f)方向的权值大于0就加到(ans_u)上。
AC代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
#define x first
#define y second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define endl '
'
const double PI=acos(-1.0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
namespace IO{
bool REOF = 1; //为0表示文件结尾
inline char nc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && REOF && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? (REOF = 0, EOF) : *p1++;
}
template<class T>
inline bool read(T &x) {
char c = nc();bool f = 0; x = 0;
while (c<'0' || c>'9')c == '-' && (f = 1), c = nc();
while (c >= '0'&&c <= '9')x = (x << 3) + (x << 1) + (c ^ 48), c = nc();
if(f)x=-x;
return REOF;
}
template<typename T, typename... T2>
inline bool read(T &x, T2 &... rest) {
read(x);
return read(rest...);
}
inline bool need(char &c) { return ((c >= 'a') && (c <= 'z')) || ((c >= '0') && (c <= '9')) || ((c >= 'A') && (c <= 'Z')); }
// inline bool need(char &c) { return ((c >= 'a') && (c <= 'z')) || ((c >= '0') && (c <= '9')) || ((c >= 'A') && (c <= 'Z')) || c==' '; }
inline bool read_str(char *a) {
while ((*a = nc()) && need(*a) && REOF)++a; *a = ' ';
return REOF;
}
inline bool read_dbl(double &x){
bool f = 0; char ch = nc(); x = 0;
while(ch<'0'||ch>'9') {f|=(ch=='-');ch=nc();}
while(ch>='0'&&ch<='9'){x=x*10.0+(ch^48);ch=nc();}
if(ch == '.') {
double tmp = 1; ch = nc();
while(ch>='0'&&ch<='9'){tmp=tmp/10.0;x=x+tmp*(ch^48);ch=nc();}
}
if(f)x=-x;
return REOF;
}
template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
while(*sdbg!=',')cerr<<*sdbg++;
cerr<<'='<<h<<','<<' '; _dbg(sdbg+1, a...);
}
template<class T> ostream &operator<<(ostream& os, vector<T> V) {
os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class T> ostream &operator<<(ostream& os, set<T> V) {
os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class T> ostream &operator<<(ostream& os, map<T,T> V) {
os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
return os << "(" << P.st << "," << P.nd << ")";
}
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
}
using namespace IO;
const int maxn=2e5+5;
const int maxv=2e5+5;
const int mod=998244353; // 998244353 1e9+7
const int INF=1e9+7; // 1e9+7 0x3f3f3f3f 0x3f3f3f3f3f3f3f3f
const double eps=1e-12;
int dx[4]={0,1,0,-1};
//int dx[8]={1,0,-1,1,-1,1,0,-1};
int dy[4]={1,0,-1,0};
//int dy[8]={1,1,1,0,0,-1,-1,-1};
// #define ls (x<<1)
// #define rs (x<<1|1)
// #define mid ((l+r)>>1)
// #define lson ls,l,mid
// #define rson rs,mid+1,r
/**
* ********** Backlight **********
* 仔细读题
* 注意边界条件
* 记得注释输入流重定向
* 没有思路就试试逆向思维
* 加油，奥利给
*/
int tot,head[maxn];
struct Edge{
int v,nxt;
Edge(){}
Edge(int _v,int _nxt):v(_v),nxt(_nxt){}
}e[maxn<<1];
void init(){
tot=1;
memset(head,0,sizeof(head));
}
void addedge(int u,int v){
e[tot]=Edge(v,head[u]); head[u]=tot++;
e[tot]=Edge(u,head[v]); head[v]=tot++;
}
void addarc(int u,int v){
e[tot]=Edge(v,head[u]); head[u]=tot++;
}
int n,a[maxn],ans[maxn],val[maxn];
void dfs1(int u,int f){
val[u]=a[u];
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(v==f)continue;
dfs1(v,u);
if(val[v]>=0)val[u]+=val[v];
}
}
void dfs2(int u,int f){
ans[u]=val[u];
if(val[u]>0)ans[f]-=val[u];
if(ans[f]>0)ans[u]+=ans[f];
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(v==f)continue;
dfs2(v,u);
}
if(val[u]>0)ans[f]+=val[u];
}
void solve(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
if(a[i]==0)a[i]=-1;
}
int u,v; init();
for(int i=1;i<=n-1;i++){
read(u,v);
addedge(u,v);
}
dfs1(1,0);
dfs2(1,0);
for(int i=1;i<=n;i++)printf("%d ",ans[i]);
}
int main()
{
// freopen("in.txt","r",stdin);
// ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// int _T; read(_T); for(int _=1;_<=_T;_++)solve();
// while(read(n))solve();
solve();
return 0;
}