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.

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.