1847: ActivateTree

Petya likes oriented graphs, especially rooted trees. He has such a tree described in a string target. Every edge may be in an active or inactive state. Initially every edge is in an inactive state. Petya wants to change the states of all the edges so that they are all active. To do so he has some trees described in a vector trees in which each element describes a single tree. Initially, every edge in target is inactive and he must activate them by repeating the following process: 1:He chooses some vertex V from target and some tree T from trees. The pair (V, T) can only be chosen once overall. 2:He chooses a subtree T‘ from target that is rooted at V and is isomorphic to T (see notes for a definition if required). 3:The state of every edge in T‘ is toggled (i.e., if it was active, it becomes inactive; if it was inactive it becomes active). Each time he follows the process he incurs a cost that depends on which tree he selected. If he selects trees[i] it costs him costs[i]. Petya also likes the number 5 and so no vertex in target will have more than 5 children. Return the minimum cost of activating all the edges in target or -1 if it is impossible to do so. target and the trees in trees will be described using the same format: The vertices are indexed sequentially starting with the root as vertex 0. The parent of each vertex in index order is then written in a space-separated list. I.e., if the i-th number written (zero-indexed) is p[i], it means that there is a directed edge from vertex p[i] to vertex i in the tree. Since the root has no parent, the first number in the list will be -1 instead. Constraints target will contain between 1 and 46 characters, inclusive. trees will contain between 1 and 5 elements inclusive. Each element of trees will contain between 4 and 10 characters. target and each element of trees will be single-space delimited lists of integers formatted without leading zeros, with no leading or trailing spaces. target will contain between 2 and 16 integers, inclusive. Each element of trees will contain between 2 and 5 integers, inclusive. The first integer in target and in each element of trees will be -1. target and each element of trees will describe valid trees as specified in the problem statement. No vertex in the tree represented by target will have more than 5 children. costs will contain the same number of elements as trees. Each element of costs will be between 0 and 65536, inclusive.

There are multiple cases ended by EOF. Each test case show up as follows: Line contain a integer n represents the number of trees. Line 2 to n + 1 each line repersents a tree. Line n + 2 represents the target. Line n + 3 contains n integers. Each integer represent the cost a tree as order.

Output the minimum cost to achieve goal that all the edges in the target is active, if it‘s impossible output -1.

1
-1 0
-1 0
5
1
-1 0
-1 0 0
5
2
-1 0
-1 0
-1 0 0
1 101
3
-1 0
-1 0
-1 0 3 0
-1 0 3 0
5 10 21
4
-1 0 1
-1 0 0
-1 0
-1 0 1 0 2
-1 0 0 0 2
3885 13122 31377 21317

5
-1
102
20
17007

Two trees T and T‘ are isomorphic if there exists a 1-to-1 mapping between the vertices of T and T‘, such that for each pair of vertices V1 and V2 in T, there is an edge (V1, V2) if and only if and edge exists between the corresponding vertices of T‘. I.e., one tree can be transformed into the other simply by relabelling the vertices.