시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 1024 MB | 9 | 3 | 3 | 33.333% |
You are given two weighted rooted trees. For each vertex, the children are ordered. You can assume they are arranged from left to right. You have four elementary operations: growing, expansion, contraction, and relabeling.
There are also some special rules:
You want to perform these operations, and change the first tree into the second tree. Output the minimum cost of doing so.
Two trees are considered the same if and only if there is a bijection from the vertices of the first tree to the vertices of the second tree that preserves the root and the order of children, and the weights of corresponding edges are the same.
The first line contains three integers $c_1$, $c_2$, and $c_3$ ($1 \leq c_1, c_2, c_3 \leq 10^6$) indicating the cost of growing (or expansion), contraction, and relabeling, respectively.
Next, the two trees are given.
For each tree, the first line contains an integer $n$ indicating the number of vertices. In the following $n$ lines, each line starts an with integer $k$ indicating the number of children, followed by $2 k$ integers $c_1, w_1, \ldots, c_k, w_k$ ($0 \leq c_i \leq 10^6$) indicating the children list and the weights of edges to children.
The size of the first tree will not be greater than $50$. The size of the second tree will not be greater than $2000$.
Output the answer.
1 1 2 4 2 2 5 4 2 1 3 1 0 0 3 2 2 1 3 2 0 0
5