7210：Independent Feedback Vertex Set

Yukikaze loves graph theory, especially forests and independent sets.

• Forest: an undirected graph without cycles.
• Independent set: a set of vertices in a graph such that for every two vertices, there is no edge connecting the two.

Yukikaze has an undirected graph $G=(V,E)$ where $V$ is the set of vertices and $E$ is the set of edges. Each vertex in $V$ has a vertex weight. Now she wants to divide $V$ into two complementary subsets $V_I$ and $V_F$ such that $V_I$ is an independent set, and the induced subgraph $G[V_F]$ is a forest. The induced subgraph $G[V_F]$ is the graph whose vertex set is $V_F$ and whose edge set consists of all of the edges in $E$ that have both endpoints in $V_F$. In addition, she wants to maximize the sum of weights of vertices in $V_I$.

Since this problem is NP-hard for general graphs, she decides to solve a special case of the problem. We can build a special graph by the following steps. Initially, the graph consists of three vertices $1,2,3$ and three edges $(1,2), (2,3), (3,1)$. When we add a vertex $x$ into the graph, we select an edge $(y,z)$ that already exists in the graph and connect $(x,y)$ and $(x,z)$. Keep doing this until there are $n$ vertices in the graph.

The first line of the input contains a single integer $T$ ($1 \leq T \leq 10^3$), indicating the number of test cases.

The first line of each test case contains a single integer $n$ ($4 \leq n \leq 10^5$), indicating the number of vertices in the graph. It is guaranteed that the sum of $n$ over all test cases won't exceed $10^6$.

The second line of each test case contains $n$ positive integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$), indicating the weights of the vertices.

Initially, the graph consists of three vertices $1,2,3$ and three edges $(1,2), (2,3), (3,1)$. The $i$-th line of the next $n-3$ lines contains two integers $u, v$ ($1 \leq u, v < i + 3$), indicating the addition of a vertex $i+3$ and two edges $(i+3,u),(i+3,v)$ to the graph. It is guaranteed that $(u,v)$ already exists in the graph.

For each test case, print an integer in a single line indicating the maximum sum of weights of vertices in $V_I$.