#P17553. [JAG 2026 Summer Camp #2] Edge Exchanges
[JAG 2026 Summer Camp #2] Edge Exchanges
题目描述
给定两棵树 和 ,每棵树都有 个顶点。两棵树具有相同的带标号顶点集 。
对于每个 (), 的第 条边连接顶点 和 。对于每个 (), 的第 条边连接顶点 和 。
对于每个 ,解决以下问题。
找到一个满足 的整数 ,使得进行下述交换后, 和 仍然都是树:
- 从 中删除连接 和 的边,从 中删除连接 和 的边。
- 然后在 中添加连接 和 的边,在 中添加连接 和 的边。
每次交换独立考虑,均从原始的树 和 开始。
可以证明,在给定约束下,对于每个 ,都至少存在一个满足要求的整数 。
输入格式
输入仅包含一组测试数据,格式如下。
N
u_1 v_1
u_2 v_2
...
u_{N-1} v_{N-1}
x_1 y_1
x_2 y_2
...
x_{N-1} y_{N-1}
整数 是 和 的顶点数()。
接下来的 行描述 的边。对于每个 ,整数 ()表示第 条边连接顶点 和 。保证 是一棵树。
再接下来的 行描述 的边。对于每个 ,整数 ()表示第 条边连接顶点 和 。保证 是一棵树。
输出格式
输出 行。对于每个 ,第 行应包含一个整数 ,使其对于 的第 条边满足题目描述中的条件。
如果有多个合法答案,可以输出任意一个。
4
1 3
2 4
3 4
1 2
2 3
2 4
1
3
2
提示
样例输出的第一行对 选择了 。将 的边 与 的边 交换后, 和 仍然都是树。
对于 , 的边和所选的 的边都是 ,因此交换它们不会改变任意一棵树。也可能存在其他合法输出。