1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
| #include <bits/stdc++.h> using namespace std; typedef long long ll; #define endl '\n' mt19937 Rand(0); const int maxn = 3e5+10; const int maxm = maxn*2; const int p = 1e9+7; ll Pow(ll x,ll d,ll p){ll ta=1;if(d==0)return 1%p;x %= p;ll a=Pow(x,d/2,p);ta=a*a%p;if(d%2)ta=ta*x%p;return ta%p;} vector<int>G[maxn],G2[maxn]; int cli[maxn],w[maxn],ans[maxn],siz[maxn]; void pre(int u,int fa,int r){ cli[u] = r; ans[u] = 1; if(r != u)w[r] += w[u]; for(int v:G2[u]){ if(v == fa)continue; if(w[u] and !ans[v])pre(v,u,r); } } void dfs(int u,int fa){ for(int v:G[u]){ if(v == fa)continue; dfs(v,u); siz[u] = max(siz[u],siz[v]); } siz[u] += w[u]; } void dfs2(int u,int fa,int res){ int tot = 0,mx1 = 0,mx2 = 0; for(int v:G[u]){ if(v == fa)continue; tot = max(tot,siz[v]); if(siz[v] >= mx1){ mx2 = mx1; mx1 = siz[v]; } else if(siz[v] > mx2)mx2 = siz[v]; } tot = max(tot,res) + w[u]; if(res >= mx1){ mx2 = mx1; mx1 = res; } else if(res > mx2)mx2 = res; if(tot > 1)ans[u] = 1; for(int v:G[u]){ if(v == fa)continue; int rw = w[u] + (mx1 == siz[v]?mx2:mx1); dfs2(v,u,rw); } } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.setf(ios::fixed,ios::floatfield); cout.precision(12); int n; cin >> n; for(int i = 1;i <= n;i++)cin >> w[i],cli[i] = i; for(int i = 1;i < n;i++){ int f,t; cin >> f >> t; G2[f].push_back(t); G2[t].push_back(f); } for(int i = 1;i <= n;i++)if(w[i] and cli[i] == i)pre(i,-1,i); for(int u = 1;u <= n;u++){ for(int v:G2[u]){ if(cli[u] == cli[v])continue; G[cli[u]].push_back(cli[v]); } } for(int i = 1;i <= n;i++){ if(cli[i] == i){ dfs(i,-1); dfs2(i,-1,0); break; } } for(int i = 1;i <= n;i++)cout << ans[i] << " "; return 0; }
|