NOI '20 P2 - Destiny

View as PDF

Submit solution

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

Problem types

Given a tree T=(V,E) (V is the set of vertices and E is the set of edges) and a set of pairs of vertices QV×V satisfying for all (u,v)Q, uv and u is an ancestor of v on tree T, you are supposed to compute how many functions f:E{0,1} (i.e. for each edge eE, the value of f(e) would be either 0 or 1) satisfies the condition for any (u,v)Q there exists an edge e on the path from u to v such that f(e)=1. Output the answer modulo 998244353.

Input Specification

The first line contains an input n denoting the number of vertices in tree T. The nodes are numbered from 1 to n and the root node is node 1. In the following n1 lines, each line contains two integers separated by a space xi,yi such that 1xi,yin denoting there exists an edge on the tree between node xi and yi. There are no guarantees for the direction of the edge. The following line contains an integer m denoting the size of Q. In the following m lines, each line contains two integers separated by a space ui,vi denoting (ui,vi)Q. There may be duplication, or in other words, there might exist some ij such that ui=uj and vi=vj.

Output Specification

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

Sample Input 1

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

Sample Output 1

Copy
10

Sample Input 2

Copy
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

Copy
960

Constraints

For all test cases, n5×105, m5×105.
The input forms a tree, where for all 1im, ui is the ancestor of vi.

Test CasenmAdditional Constraints
11010None.
2
3
4
550015
61000010
710000016
8500000
910000022
10500000
11600600
1210001000
132000500000
14
155000002000
16
17100000100000See below.
18
1950000None.
2080000
21100000500000
22
23500000
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.


Comments

There are no comments at the moment.