6598: 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 VI and VF such that VI is an independent set, and the induced subgraph G[VF] is a forest. The induced subgraph G[VF] is the graph whose vertex set is VF and whose edge set consists of all of the edges in E that have both endpoints in VF. In addition, she wants to maximize the sum of weights of vertices in VI.

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≤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≤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.