# Tree Permutations TREEPERM Solution

Page Contents

## 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
Subtask #1 (40 points): the sum of N over all test cases does not exceed 1,000
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 {,[2,3]} and {[1,2,3]}.

Example case 2: The good vertical partitions are:

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

Example case 4: There is no good vertical partition.