3662: 划分(第二轮04)
题目描述
牛牛有一棵 n个节点的有根树，节点编号为 1 到 n，根节点为 1。节点 i上写有数 字 ai 。
我们称一条直链为一条 u到v的路径， 其中 u是 v的祖先或 u = v（注意：这里的 直链和链的定义不同）。
牛牛想要将这棵树划分成若干直链，满足每个节点恰好属于一条直链，如果对于 划分出的每条直链，将该链上的点上写的数字任意排列，最后的结果满足对于任
意节点 i，节点 i上写的数字为 bi，那我们就称这种划分方案是好的。 你需要回答牛牛是否存在好的划分方案。
输入
本题有多组数据。第一行一个整数 T，表示数据组数。 每组数据格式如下：
第一行一个整数 n，表示树的节点数量。
接下来 n − 1行，第 i行两个整数 xi, yi，表示树中存在一条边 (xi, yi)。
接下来一行， n个整数， a1, a2, … , an 。 接下来一行， n个整数， b1, b2, … , bn 。
输出
输出一行一个字符串 Yes 或者 No，表示是否存在好的划分方案 。
样例输入 复制
2
6
1 2
1 3
2 4
3 5
3 6
1 2 3 4 5 6
1 4 5 2 3 6
6
6 4
4 2
3 1
2 1
5 3
6 9 8 8 10 10
8 6 1 3 10 1样例输出 复制
Yes
No提示
【样例 1 输入】
2
6
1 2
1 3
2 4
3 5
3 6
1 2 3 4 5 6
1 4 5 2 3 6
6
6 4
4 2
3 1
2 1
5 3
6 9 8 8 10 10
8 6 1 3 10 1
【样例 1 输出】
Yes
No
【样例 2 】
选手目录： https://uploadfiles.nowcoder.com/files/20211004/partition.zip 见选手目录下的 partition/partition2.in 和 partition/partition2.ans。
【样例 3 】
见选手目录下的 partition/partition3.in 和 partition/partition3.ans。 该样例满足 a1, a2, … , an 互不相同， b1, b2, … , bn 互不相同。
【数据范围】
对于 10% 的数据， n ≤ 8。
对于 30% 的数据， n ≤ 18 。 对于 50% 的数据， n ≤ 100。
对于 60% 的数据， T ≤ 5, n ≤ 1000。
对于另外 20% 的数据， a1, a2, … , an 互不相同， b1, b2, … , bn 互不相同。 对于 90% 的数据， ∑n ≤ 10^5 。
对于 100% 的数据， 1 ≤ T ≤ 10^3， 1 ≤ n ≤ 10^5， ∑n ≤ 10^6， 1 ≤ xi, yi ≤ n， 1 ≤ ai, bi ≤ 10^6，输入保证是一棵树。