Tree Permutations TREEPERM Solution

Tree Permutations TREEPERM April Long Challenge 2021

You are given a tree with N nodes (numbered 1 through N), rooted at node 1. For each valid i, node i has a value ai written on it.

An undirected simple path between any two nodes u and v is said to be vertical if u=v or u is an ancestor of v or v is an ancestor of u. Let’s define a vertical partition of the tree as a set of vertical paths such that each node belongs to exactly one of these paths.

You are also given a sequence of N integers b1,b2,…,bN. A vertical partition is good if, for each of its paths, we can permute the values written on the nodes in this path, and this can be done in such a way that we reach a state where for each valid i, the value written on node i is bi.

The difficulty of your task is described by a parameter S. If S=1, your task is only to determine whether at least one good vertical partition exists. If S=2, you are required to find the number of good vertical partitions modulo 1,000,000,007 (109+7).

Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and S.
Each of the next N−1 lines contains two space-separated integers u and v denoting that nodes u and v are connected by an edge.
The next line contains N space-separated integers a1,a2,…,aN.
The line after that contains N space-separated integers b1,b2,…,bN.
Output
For each test case, print a single line containing one integer:

If S=1, this integer should be 1 if a good vertical partition exists or 0 if it does not exist.
If S=2, this integer should be the number of good vertical partitions modulo 1,000,000,007 (109+7).
Constraints
1≤T≤106
1≤N≤105
S∈{1,2}
1≤u,v≤N
the graph described on the input is a tree
1≤ai,bi≤106 for each valid i
the sum of N over all test cases does not exceed 106
Subtasks
Subtask #1 (40 points): the sum of N over all test cases does not exceed 1,000
Subtask #2 (30 points): S=1
Subtask #3 (30 points): original constraints

Example Input
4
3 2
1 2
2 3
4 5 6
4 6 5
6 2
1 2
1 3
2 4
3 5
3 6
10 20 30 40 50 60
10 40 50 20 30 60
6 1
1 2
1 3
2 4
3 5
3 6
10 20 30 40 50 60
10 40 50 20 30 60
1 2
1
2
Example Output
2
3
1
0
Explanation
Example case 1: The good vertical partitions are {[1],[2,3]} and {[1,2,3]}.

Example case 2: The good vertical partitions are:

{[1,2,4],[3,5],[6]}
{[1],[2,4],[3,5],[6]}
{[1,3,5],[2,4],[6]}
Example case 3: The same as example case 2, but with S=1.

Example case 4: There is no good vertical partition.

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

1. Frog Sort Solution Codechef

2. Chef and Meetings Solution Codechef

3. Maximise Function Solution Codechef

4. Highest Divisor Solution Codechef

5. Cut the Cake Challenge Solution Codechef

6. Dream and the Multiverse Solution Codechef

7. Cell Shell Solution Codechef

8. Multiple Games Solution Codechef

9. Another Tree with Number Theory Solution Codechef

10. XOR Sums Solution Codechef

11. Prime Game Solution CodeChef

12. Team Name Solution Codechef

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

RELATED :

Related :

Related :

Leave a Comment