8625: 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.

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 $)$. 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≤T≤103), indicating the number of test cases.

The first line of each test case contains a single integer n 4≤n≤105), indicating the number of vertices in the graph. It is guaranteed that the sum of $n$ over all test cases won't exceed 106.

The second line of each test case contains n positive integers a1,a2,…,an (1≤ai≤109), 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\le u,v<i+3$), indicating the addition of a vertex i+3 and two edges $(i+3,v)$ to the graph. It is guaranteed that (u,v) already exists in the graph.

3
4
3 3 2 2
1 2
4
2 5 5 2
2 3
5
3 1 1 1 1
1 2
1 3

4
5
3