New Online Judge 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

1834: [NewOJ Week 9] 树与排列

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：126 通过：38
提交提交记录统计

题目描述

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

输入格式

第一行为正整数T，表示存在T组测试数据，T≤50000。
对于每组测试数据，第一行输入n，表示树的节点数量，节点编号为1-n，2≤n≤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