6598: Independent Feedback Vertex Set
内存限制:128 MB
时间限制:3.000 S
评测方式:文本比较
命题人:
提交:1
解决:1
题目描述
Yukikaze loves graph theory, especially forests and independent sets.
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.
- 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 (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.
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.
输出
For each test case, print an integer in a single line indicating the maximum sum of weights of vertices in VI.
样例输入 复制
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