牛魔！

题号：NC317835
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定一棵包含 $n$ 个节点的有根树，节点编号为 $1\sim n$ ，根节点为 $1$ 。每个节点有一个权值，权值只可能为 $0$ 或 $1$ 。
$\hspace{15pt}$ 一次操作可以选择一个既不是根节点也不是叶子节点的节点 $i$ ，再选择节点 $i$ 的任意一个孩子节点 $j$ ，然后同时将节点 $i$ 、节点 $i$ 的父节点、节点 $j$ 的权值取反，即 $0$ 变 $1$ ， $1$ 变 $0$ 。
$\hspace{15pt}$ 你可以进行任意多次操作。请问操作结束后，整棵树所有节点权值之和的最大可能值是多少。

【名词解释】
$\hspace{15pt}$ 叶子节点：如果一个节点没有任何子节点（即度为 $1$ ，且不是根节点，或在只有一个节点的情况下为根节点），则称其为叶子节点。
$\hspace{15pt}$ 孩子节点：也称子节点。在一棵有根树中，所有与节点 $u$ 直接相连，且距离根节点比 $u$ 更远的节点，均称为 $u$ 的孩子节点。
$\hspace{15pt}$ 父节点：在一棵有根树中，从根节点到任意节点 $u$ 的路径上，与 $u$ 直接相连的那个节点称为 $u$ 的父节点。根节点没有父节点。

输入描述:

第一行一个整数 ，表示树的节点数。
第二行包含  个整数，为 ，表示每个节点的初始权值。
接下来  行，每行两个整数 ，表示树上的一条无向边。

输出描述:

输出一行一个整数，表示经过任意多次操作后，整棵树所有节点权值之和的最大可能值。

示例1

输入

复制

输出

复制

说明

解释：选择节点  和它的儿子节点  进行一次操作，可以同时将节点  的权值取反，最终三个节点权值均为 。

示例2

输入

复制

输出

复制

说明

解释：可以选择节点  和它的儿子节点  进行一次操作，节点  的权值取反后，权值为  的节点数达到 。可以证明无法得到更多权值为  的节点。