1004. 用一棵树给另一棵树染色

题目描述

给定两棵点集均为 $1$ 到 $n$ 的树，分别称为第一棵树和第二棵树。第一棵树的所有边初始均为白色。

你可以执行任意多次以下操作：

选择第二棵树中的一条边 $(u,v)$，考虑第一棵树上从 $u$ 到 $v$ 的简单路径。

• 如果路径上的所有边均为白色，则选择路径上的一条边，将其染成黑色；
• 如果路径上至少存在一条黑色边，则不进行任何染色。

判断是否存在一种操作方案，使第一棵树的所有边最终均为黑色。

输入格式

第一行输入一个整数 $T$，表示测试数据组数。

每组测试数据的格式如下：

第一行输入一个整数 $n$，表示两棵树的点数。

接下来 $n-1$ 行，每行输入两个整数 $u,v$，表示第一棵树中存在一条无向边 $(u,v)$。

接下来 $n-1$ 行，每行输入两个整数 $u,v$，表示第二棵树中存在一条无向边 $(u,v)$。

对于一组测试数据：

$1\le n\le 10^6$；

$1\le u,v\le n$；

输入保证两部分给出的图均为树。

只有一个正式测试点，该测试点满足：

$T=10000$；

$\sum n=10^7$。

输出格式

对于每组测试数据输出一行。

如果可以使第一棵树的所有边均变成黑色，输出 YES；否则输出 NO。

样例输入

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

样例输出

YES
NO
YES

提示

样例解释

对于第一组测试数据，第一棵树是一条链 $1-2-3-4-5$。

可以依次进行以下操作：

• 选择第二棵树中的边 $(1,5)$，将第一棵树中的边 $(4,5)$ 染成黑色；
• 选择第二棵树中的边 $(1,4)$，将第一棵树中的边 $(1,2)$ 染成黑色；
• 选择第二棵树中的边 $(2,4)$，将第一棵树中的边 $(2,3)$ 染成黑色；
• 选择第二棵树中的边 $(3,4)$，将第一棵树中的边 $(3,4)$ 染成黑色。

此时第一棵树的所有边均为黑色，因此答案为 YES。

对于第二组测试数据，不存在满足要求的操作方案，因此答案为 NO。

对于第三组测试数据，两棵树均只有边 $(1,2)$。选择第二棵树中的这条边，将第一棵树中的边 $(1,2)$ 染成黑色即可。

来源：2026杭电多校-测试专用（肖岱恩） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1236&pid=1004