CF2258F.Plus Minus Tree

You are given a tree $T$ with $n$ vertices, rooted$^{\text{∗}}$ at vertex $1$. Each vertex $v$ is assigned an initial weight $ a_v \in { -1, 0, +1 } $.

For each vertex with weight $0$, you have to assign a new weight, either $-1$ or $+1$. Let $x_v$ be the final weight of vertex $v$.

For vertex $v$, let $T_v$ be the set of nodes in the subtree$^{\text{†}}$ of vertex $v$. The cost of vertex $v$ is defined as $$ S_v = \left| \sum_{u \in T_v}{x_u} \right|.$$

The total cost of the tree is defined as the sum of costs over all vertices. Find the minimum possible total cost of the tree after assigning the weights of all vertices with zero initial weight.

$^{\text{∗}}$A tree is a connected graph without cycles. A rooted tree is a tree where one vertex is special and called the root.

$^{\text{†}}$A subtree of vertex $v$ is the subgraph consisting of $v$, all its descendants, and all the edges between them. A descendant of vertex $v$ is any vertex $u$ for which $v$ is an ancestor. No vertex is its own descendant. An ancestor of vertex $v$ is any vertex on the simple path from $v$ to the root, including the root, but not including $v$. The root has no ancestors.

给你一棵有 $n$ 个顶点的树 $T$，以顶点 $1$ 为根$^{\text{∗}}$。每个顶点 $v$ 被赋予一个初始权重 $ a_v \in { -1, 0, +1 } $。

对每个初始权重为 $0$ 的顶点，你必须为其重新指定一个新权重，取值为 $-1$ 或 $+1$。记顶点 $v$ 的最终权重为 $x_v$。

对顶点 $v$，令 $T_v$ 表示顶点 $v$ 的子树$^{\text{†}}$ 中所有节点的集合。顶点 $v$ 的代价定义为

$$S\_v = \left| \sum\_{u \in T\_v}{x\_u} \right|.$$

整棵树的总代价定义为所有顶点代价之和。在为所有初始权重为零的顶点分配权重后，求整棵树可能的最小总代价。

$^{\text{∗}}$ 树是一个无环连通图。有根树是一棵指定了一个特殊顶点作为根的树。

$^{\text{†}}$ 顶点 $v$ 的子树是指由 $v$、$v$ 的所有后代以及它们之间的所有边构成的子图。顶点 $v$ 的后代是指任意满足 $v$ 是其祖先的顶点 $u$；任何顶点均不是自身的后代。顶点 $v$ 的祖先是指从 $v$ 到根节点的简单路径上的所有顶点（包括根节点，但不包括 $v$ 自身）。根节点没有祖先。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains $n$ ($2 \le n \le 2 \cdot 10^5$), denoting the number of vertices in the tree.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-1 \le a_i \le 1$).

Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$), denoting the nodes connected with an edge of the tree. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示树中顶点的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-1 \le a_i \le 1$）。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示树中一条边所连接的两个节点。保证所给的边构成一棵树。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, print the minimum total cost of the tree.

对于每个测试用例，输出该树的最小总成本。

The best assignments in the first test case are $[+1, +1, -1, -1, +1]$ and $[-1, +1, -1, -1, +1]$. They have a cost of $5$.

Another assignment, $[+1, +1, -1, +1, +1]$ has a cost of $9$, and $[-1, +1, -1, +1, +1]$ has a cost of $7$.

The tree of the first testcase

The tree of the second testcase

第一个测试用例中最优的赋值方案为 $[+1, +1, -1, -1, +1]$ 和 $[-1, +1, -1, -1, +1]$，它们的代价均为 $5$。

另一组赋值方案 $[+1, +1, -1, +1, +1]$ 的代价为 $9$，而 $[-1, +1, -1, +1, +1]$ 的代价为 $7$。

第一个测试用例对应的树

第二个测试用例对应的树