1834: [NewOJ Week 9] 树与排列

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:46 通过:9

题目描述

给你一棵树和它的顶点的排列。
可以证明:对于任何树,任何一对源点/终点,存在排列第一个节点是源点,最后一个节点是终点,排列的相邻节点之间的距离小于或等于3。
你的任务是为该性质编写一个验证程序。
给定这样一个排列和树,验证排列中相邻节点之间的距离是否小于或等于3。

输入格式

第一行为正整数T,表示存在T组测试数据,T50000。
对于每组测试数据,第一行输入n,表示树的节点数量,节点编号为1-n,2n≤100000。
接下来n-1行,每行两个数字a和b,表示节点a和b之间存在边。
接下来n行,每行一个数字p,表示给定的排列。
输入保证n总和不超过100000。

输出格式

对于每组测试数据,表示满足题目条件输出1,否则输出0。

输入样例 复制

2
5
1 2
2 3
3 4
4 5
1
3
2
5
4
5
1 2
2 3
3 4
4 5
1
5
2
3
4

输出样例 复制

1
0