Codeforces Round #627 (Div. 3)F. Maximum White Subtree
题：https://codeforces.com/contest/1324/problem/F
题意：给节点数为n的树，每个节点有0和1，对于每个节点输出他的ans，这个ans是砍掉一些子树后0节点的数目减去1节点的数目（得留下自己）
分析：我们按照统计子树的size一样，来dfs这个树，对于父亲u和儿子v,儿子有贡献才向上传，这次dfs完后我们只能求出根节点的ans值；
我们就利用根节点dfs算出接下来的ans值
#include<bits/stdc++.h> using namespace std; #define pb push_back const int M=2e5+5; int ans[M],a[M]; vector<int>g[M]; int dfs1(int u,int fa){ int tmp; if(a[u]==1) tmp=1; else tmp=-1; for(auto v:g[u]){ if(v!=fa){ int x=dfs1(v,u); tmp+=max(0,x); } } return ans[u]=tmp; } void dfs2(int u,int fa){ if(fa!=0){ int tmp=ans[fa]; tmp-=max(0,ans[u]); ans[u]+=max(0,tmp); } for(auto v:g[u]){ if(v!=fa) dfs2(v,u); } } int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int u,v,i=1;i<n;i++){ scanf("%d%d",&u,&v); g[u].pb(v); g[v].pb(u); } dfs1(1,0); dfs2(1,0); for(int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; }