#P12936. [AGC014E] Blue and Red Tree

    ID: 12120 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-逆向思考普通并查集按大小合并小并大合并集合有序集合

[AGC014E] Blue and Red Tree

题目描述

有一棵包含 NN 个顶点的树,顶点编号为 11 到 NN。此外,N−1N-1 条边中,第 ii 条边连接顶点 aia_i 和顶点 bib_i。

初始情况下,所有边都被涂成蓝色。之后,高桥君将进行如下操作 N−1N-1 次,将这棵树转换为一棵红色的树:

  • 从只包含蓝色边的路径中选择一条,从该路径上删去一条边。
  • 随后,在一开始选的那条路径的两个端点之间添加一条红色的边。

最终,他希望得到一棵新的树,包含 NN 个顶点且满足下列性质:对于每个 ii,存在一条红色的边直接连接顶点 cic_i 和顶点 did_i。

请判断高桥君能否完成这样的目标。

输入格式

输入从标准输入读入,格式如下:

NN a1a_1 b1b_1 … aN−1a_{N-1} bN−1b_{N-1} c1c_1 d1d_1 … cN−1c_{N-1} dN−1d_{N-1}

输出格式

如果高桥君能够将初始的树成功改造成目标树,则输出 YES。否则输出 NO。

输入输出样例 #1

输入 #1

3
1 2
2 3
1 3
3 2

输出 #1

YES

输入输出样例 #2

输入 #2

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

输出 #2

YES

输入输出样例 #3

输入 #3

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

输出 #3

NO

说明/提示

约束条件

  • 2≤N≤1052 \leq N \leq 10^5
  • 1≤ai,bi,ci,di≤N1 \leq a_i, b_i, c_i, d_i \leq N
  • ai≠bia_i \neq b_i
  • ci≠dic_i \neq d_i
  • 输入给定的两组边分别构成一棵树。

样例解释 1

高桥君可以按照如下顺序构造目标红色树:

  • 首先,选择连接顶点 11 和 33 的路径,并删去蓝色的边 1−21-2,再加入红色的边 1−31-3。
  • 接着,选择连接顶点 22 和 33 的路径,并删去蓝色的边 2−32-3,再加入红色的边 2−32-3。