F - Maximum White Subtree

You are given a tree consisting of nn vertices. A tree is a connected undirected graph with n−1n−1 edges. Each vertex vv of this tree has a color assigned to it (av=1av=1 if the vertex vv is white and 00 if the vertex vvis black).

You have to solve the following problem for each vertex vv: what is the maximum difference between the number of white and the number of black vertices you can obtain if you choose some subtree of the given tree that contains the vertex vv? The subtree of the tree is the connected subgraph of the given tree. More formally, if you choose the subtree that contains cntwcntw white vertices and cntbcntb black vertices, you have to maximize cntw−cntbcntw−cntb.

Input

The first line of the input contains one integer nn (2≤n≤2⋅1052≤n≤2⋅105) — the number of vertices in the tree.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (0≤ai≤10≤ai≤1), where aiai is the color of the ii-th vertex.

Each of the next n−1n−1 lines describes an edge of the tree. Edge ii is denoted by two integers uiui and vivi, the labels of vertices it connects (1≤ui,vi≤n,ui≠vi(1≤ui,vi≤n,ui≠vi).

It is guaranteed that the given edges form a tree.

Output

Print nn integers res1,res2,…,resnres1,res2,…,resn, where resiresi is the maximum possible difference between the number of white and black vertices in some subtree that contains the vertex ii.

Examples

Input

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

2 2 2 2 2 1 1 0 2 

Input

4
0 0 1 0
1 2
1 3
1 4

Output

0 -1 1 -1 

一开始想到的是树形dp，用了dfs

int DFS(int x) {
    book[x] = 1;
    int sum = v[x];
    for (vector<int>::iterator i = tree[x].begin(); i != tree[x].end(); i++) {
        if (book[(*i)] == 0) {
            int t = DFS(*i);
            if (t > 0) {
                sum += t;
            }
        }
    }
    if (sum < 0) {
        sum = 0;
    }
    return sum;
}

但是很不幸，在某一组样例时间超限了

仔细思考了一下，感觉可能是因为每一个根都进行了一次dfs，浪费了太多时间，同时产生了不必要的运算

于是尝试用数组记录了第一遍dfs得出的值，然后再用一遍反向的dfs用来补充第一遍因为按顺序运算没有计算的差值

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

#define T 200001

vector<int> tree[T];
int v[T], book[T], dp[T];


void DFS(int x) {
    book[x] = 1;
    dp[x] = v[x];
    for (vector<int>::iterator i = tree[x].begin(); i != tree[x].end(); i++) {
        if (book[(*i)] == 0) {
            DFS(*i);
            if (dp[(*i)] > 0) {
                dp[x] += dp[(*i)];
            }
        }
    }
}

void FanXiang_DFS(int x) {
    book[x] = 1;
    for (vector<int>::iterator i = tree[x].begin(); i != tree[x].end(); i++) {
        if (book[(*i)] == 0) {
            dp[(*i)] += max(0, dp[x] - max(0, dp[(*i)]));
            FanXiang_DFS((*i));
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
        if (v[i] == 0) {
            v[i] = -1;
        }
    }
    for (int i = 1; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    memset(book, 0, sizeof(book));
    book[1] = 1;
    DFS(1);
    memset(book, 0, sizeof(book));
    book[1] = 1;
    FanXiang_DFS(1);
    for (int i = 1; i <= n; i++) {
        printf("%d ", dp[i]);
    }
    

    return 0;
}

F - Maximum White Subtree

原文：https://www.cnblogs.com/Vetsama/p/12531427.html