## NOI '20 P2 - Destiny

View as PDF

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 1G

Problem type

Given a tree ( is the set of vertices and is the set of edges) and a set of pairs of vertices satisfying for all , and is an ancestor of on tree , you are supposed to compute how many functions (i.e. for each edge , the value of would be either or ) satisfies the condition for any there exists an edge on the path from to such that . Output the answer modulo .

#### Input Specification

The first line contains an input denoting the number of vertices in tree . The nodes are numbered from 1 to and the root node is node 1. In the following lines, each line contains two integers separated by a space such that denoting there exists an edge on the tree between node and . There are no guarantees for the direction of the edge. The following line contains an integer denoting the size of . In the following lines, each line contains two integers separated by a space denoting . There may be duplication, or in other words, there might exist some such that and .

#### Output Specification

The output contains only an integer denoting the number of functions satisfying the condition above.

#### Sample Input 1

5
1 2
2 3
3 4
3 5
2
1 3
2 5

#### Sample Output 1

10

#### Sample Input 2

15
2 1
3 1
4 3
5 2
6 3
7 6
8 4
9 5
10 7
11 5
12 10
13 3
14 9
15 8
6
3 12
5 11
2 5
3 13
8 15
1 13

#### Sample Output 2

960

#### Constraints

For all test cases, , .
The input forms a tree, where for all , is the ancestor of .

Test Case  Additional Constraints
1  None.
2
3
4
5  6  7  8 9  10 11  12  13  14
15  16
17  See below.
18
19 None.
20 21  22
23 24
25

In this problem, a perfect binary tree is a binary tree such that each non-leaf node has two children and the depths of all leaf nodes are the same; if we number the nodes in a perfect binary tree from up to down, from left to right, the tree formed by the nodes with smallest numbers form a complete binary tree. Test cases 17 and 18 are complete binary trees.