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 Q \subset V \times V satisfying for all (u,v) \in Q, u \ne v and u is an ancestor of v on tree T, you are supposed to compute how many functions f: E \to \{0, 1\} (i.e. for each edge e \in E, the value of f(e) would be either 0 or 1) satisfies the condition for any (u,v) \in Q there exists an edge e on the path from u to v such that f(e) = 1. Output the answer modulo 998\,244\,353.

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 n-1 lines, each line contains two integers separated by a space x_i, y_i such that 1 \le x_i,y_i \le n denoting there exists an edge on the tree between node x_i and y_i. 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 u_i,v_i denoting (u_i,v_i) \in Q. There may be duplication, or in other words, there might exist some i \ne j such that u_i = u_j and v_i = v_j.

Output Specification

The output contains only an integer denoting the number of functions f 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, n \le 5 \times 10^5, m \le 5 \times 10^5.
The input forms a tree, where for all 1 \le i \le m, u_i is the ancestor of v_i.

Test CasenmAdditional Constraints
1\le 10\le 10None.
2
3
4
5\le 500\le 15
6\le 10\,000\le 10
7\le 100\,000\le 16
8\le 500\,000
9\le 100\,000\le 22
10\le 500\,000
11\le 600\le 600
12\le 1000\le 1000
13\le 2000\le 500\,000
14
15\le 500\,000\le 2000
16
17\le 100\,000\le 100\,000See below.
18
19\le 50\,000None.
20\le 80\,000
21\le 100\,000\le 500\,000
22
23\le 500\,000
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.