F. Maximum White Subtree

You are given a tree consisting of

You have to solve the following problem for each vertex

Input

The first line of the input contains one integer

The second line of the input contains

Each of the next

It is guaranteed that the given edges form a tree.

Output

Examples

input

Copy

9
0 1 1 1 0 0 0 0 1
1 2
1 3
3 4
3 5
2 6
4 7
6 8
5 9

output

Copy

2 2 2 2 2 1 1 0 2

input

Copy

output

Copy

0 -1 1 -1

Note

The first example is shown below:

$F. Maximum White Subtree$

The black vertices have bold borders.

In the second example, the best subtree for vertices

两次dfs

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <deque>
#include <bitset>
//#include <unordered_set>
//#include <unordered_map>
#define ll              long long
#define pii             pair<int, int>
#define rep(i,a,b)      for(int  i=a;i<=b;i++)
#define dec(i,a,b)      for(int  i=a;i>=b;i--)
#define forn(i, n)      for(int i = 0; i < int(n); i++)
using namespace std;
int dir[4][2] = { { 1,0 },{ 0,1 } ,{ 0,-1 },{ -1,0 } };
const long long INF = 0x7f7f7f7f7f7f7f7f;
const int inf = 0x3f3f3f3f;
const double pi = 3.14159265358979323846;
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
//if(x<0 || x>=r || y<0 || y>=c)

inline ll read()
{
    ll x = 0; bool f = true; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = false; c = getchar(); }
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return f ? x : -x;
}
ll gcd(ll m, ll n)
{
    return n == 0 ? m : gcd(n, m % n);
}
ll lcm(ll m, ll n)
{
    return m * n / gcd(m, n);
}
bool prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0) return false;
    }
    return true;
}
ll qpow(ll m, ll k, ll mod)
{
    ll res = 1, t = m;
    while (k)
    {
        if (k & 1)
            res = res * t % mod;
        t = t * t % mod;
        k >>= 1;
    }
    return res;
}
vector<int> a(N),dp(N),ans(N),node[N];
void dfs1(int u, int fa)
{
    dp[u] = a[u];
    for (auto v : node[u])
    {
        if (v == fa)
            continue;
        dfs1(v, u);
        dp[u] += max(dp[v], 0);
    }
}
void dfs2(int u, int fa, int sum)
{
    ans[u] = dp[u] + sum;
    for (auto v : node[u])
    {
        if (v == fa)
            continue;
        dfs2(v, u, max(0, ans[u] - max(0, dp[v])));
    }
}
int main()
{
    int n;
    cin >> n;
    rep(i, 1, n)
    {
        cin >> a[i];
        if (a[i] == 0)
            a[i] = -1;
    }
    rep(i, 1, n-1)
    {
        int u, v;
        cin >> u >> v;
        node[u].push_back(v);
        node[v].push_back(u);
    }
    dfs1(1, -1);
    dfs2(1, -1, 0);
    rep(i, 1, n)
        cout << ans[i] << " ";
    return 0;
}

相关推荐