## NOIP '18 P6 - Defending the Kingdom

View as PDF

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem types

Given a tree with vertices such that each vertex has an associated cost . There are queries: if vertex must or must not be chosen and vertex must or must not be chosen, what is the minimum cost of a vertex cover (i.e. minimum cost to choose a subset of vertices such that for all edges at least one endpoint is in the subset). If vertex covers do not exist under the constraint given in a query, output -1.

#### Input Specification

The first line contains two integers and one string . represents the number of vertices, represents the number of queries, and represents additional constraints satisfied by the test case.

The second line contains integers denoting the cost associated with vertex .

In the following lines, each line contains two integers denoting there exists an edge in the tree.

In the following lines, each line contains 4 integers . If , then vertex cannot be included in the vertex cover, while if vertex must be in the vertex cover. Similarly, if , vertex cannot be included in the vertex cover, while if , vertex must be in the vertex cover.

#### Output Specification

The output consists of lines. Each line contains an integer: the -th line denotes the minimum cost of a vertex cover satisfying the constraints outlined in the -th query. If it is impossible to have a vertex cover satisfying the constraint, output -1.

#### Sample Input 1

5 3 C3
2 4 1 3 9
1 5
5 2
5 3
3 4
1 0 3 0
2 1 3 1
1 0 5 0

#### Sample Output 1

12
7
-1

For the first query, the subset of vertices shall be .

For the second query, the subset of vertices shall be .

The constraints in the last query cannot be satisfied since both endpoints of edge cannot be in the vertex cover.

Additional samples can be found here.

#### Constraints

For all test cases, , .

Test Case Type
1-2 A3
3-4 C3
5-6 A3
7 C3
8-9 A3
10-11 C3
12-13 A1
14-16 A2
17 A3
18-19 B1
20-21 C1
22 C2
23-25 C3

Interpretation of :

• A - vertex and are connected directly by an edge.

• B - if the tree's root is vertex , then the depth is at most .

• C - no additional constraints on the tree.

• 1 - for all queries, , (i.e. vertex must be included). There are no constraints on and .

• 2 - in a query, vertex and are guaranteed to be adjacent.

• 3 - no additional constraints on the queries.