2E. Merge Three Vertices

You are given a tree with $n$ vertices. Each vertex $v$ has an integer value $a_v$ (it may be negative).

In one operation, choose three distinct vertices $v,u,w$ such that $v$ is adjacent to $u$ and $u$ is adjacent to $w$, so $v-u-w$ is a path of length $2$ and $u$ is the middle vertex.

Then vertices $v$ and $w$ are deleted, and vertex $u$ stays. For every former neighbor $x$ of $v$ with $x \ne u$, add an edge between $x$ and $u$. For every former neighbor $y$ of $w$ with $y \ne u$, add an edge between $y$ and $u$. The value of $u$ remains $a_u$. After this operation, the graph is still a tree.

You may perform any number of operations (possibly zero). Your goal is to maximize the sum of values of the remaining vertices.

Constraints

• $1 \le t \le 100$
• $1 \le n \le 2 \times 10^5$
• $-10^9 \le a_v \le 10^9$
• The sum of $n$ over all test cases does not exceed $2 \times 10^5$