#2873. 划分

划分

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

牛牛有一棵 n\red{n}个节点的有根树,节点编号为 1\red{1 }n\red{n,}根节点为 1\red{1}。节点 i\red{i}上写有数 字 ai\red{a_i }

我们称一条直链为一条 u\red{u}v\red{v}的路径,其中 u\red{u}v\red{v}的祖先或 u=v\red{u = v(}注意:这里的 直链和链的定义不同)。

牛牛想要将这棵树划分成若干直链,满足每个节点恰好属于一条直链,如果对于 划分出的每条直链,将该链上的点上写的数字任意排列,最后的结果满足对于任 意节点 i\red{i,}节点 i\red{i}上写的数字为 bi\red{b_i,}那我们就称这种划分方案是好的。

你需要回答牛牛是否存在好的划分方案。

输入格式

本题有多组数据。第一行一个整数 T\red{T,}表示数据组数。

每组数据格式如下:

第一行一个整数 n\red{n,}表示树的节点数量。

接下来 n1\red{n -1}行,第 i\red{i}行两个整数 xi,yi\red{x_i, y_i,}表示树中存在一条边 (xi,yi)\red{(x_i, y_i)}

接下来一行,n\red{n}个整数, a1,a2,...,an\red{a_1, a_2,... , a_n }

接下来一行,n\red{n}个整数,b1,b2,...,bn\red{b_1, b_2,..., b_n}

输出格式

输出一行一个字符串 Yes\red{Yes }或者 No\red{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

提示

对于 10%\red{10\% }的数据,n\red{n ≤} 8\red{8}

对于 30%\red{30\% }的数据,n\red{n ≤} 18\red{18}

对于 50%\red{50\% }的数据,n\red{n ≤} 100\red{100}

对于 60%\red{60\% }的数据,T\red{T ≤} 5,n\red{5, n ≤} 1000\red{1000}

对于另外 20%\red{20\% }的数据, a1,a2,...,an\red{a_1, a_2,..., a_n}互不相同,b1,b2,...,bn\red{b_1, b_2,..., b_n }互不相同。

对于 90%\red{90\% }的数据,n\red{∑n ≤} 105\red{10^5 }

对于 100%\red{100\% }的数据,1\red{1 ≤} T\red{T ≤} 103\red{10^3,}1\red{1 ≤} n\red{n ≤} 105\red{10^5,}n\red{∑n ≤} 106\red{10^6,}1\red{1 ≤} xi,yi\red{x_i, y_i ≤} n\red{n,}1\red{1 ≤} ai,bi\red{a_i, b_i ≤} 106\red{10^6,}输入保证是一棵树。

2022CSP—J2模拟赛2

未参加
状态
已结束
规则
OI
题目
4
开始于
2022-10-2 19:30
结束于
2022-10-2 23:00
持续时间
3.5 小时
主持人
参赛人数
50