shunfurh
编程介的小学生
2018-12-05 08:38
采纳率: 92.7%
浏览 472

用颜色标记一颗二叉树的算法,用C语言怎么实现?

Problem Description
Bob intends to color the nodes of a tree with a pen. The tree consists of N nodes. These nodes are numbered 1,2,...,N. The root of the tree is node 1. The initial color of each node is white. Bob can use one unit energy to color one node into black. To prevent Bob being lazy with painting, Alice proposed A+B rules. Each rule is represent by two numbers xi and yi.
For the first A rules, it means that there should be no less than yi nodes painted black for the subtree of node xi.
For the other B rules, it means that there should be no less than yi nodes painted black for all nodes except the subtree of node xi.
You need to help Bob to calculate the minimum energy he needs for the painting with all rules proposed by Alice satisfied.

Input
The first line is the number of test cases. For each test case, the first line contains one positive number N(1≤N≤100000), indicating the number of trees nodes.

The following N−1 lines describe the edges. Each line contains two integers u,v(1≤u,v≤N), denoting there is a edge between node u and node v.

The following one line contains one number A(A≤100000), indicating the first A rules.

The following A lines describe the first A rules. Each line contains two numbers xi and yi as described above.

The following one line contains one number B(B≤100000), indicating the other B rules.

The following B lines describe the other B rules. Each line contains two numbers xi and yi as described above.

Output
For each test case, output a integer donating the minimum energy Bob needs to use with all rules propose by Alice satisfied. If there is no solution, output −1 instead.

Sample Input
2
5
1 2
2 3
3 4
1 5
2
2 1
5 1
1
2 1
5
1 2
2 3
3 4
1 5
3
1 2
2 2
5 1
1
3 5

Sample Output
2
-1

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

相关推荐