33OJ
登录 注册

#P17553. [JAG 2026 Summer Camp #2] Edge Exchanges

    ID: 20279 远端评测题 2000ms 2048MiB 尝试: 0 已通过: 0 显示难度提高+/省选− 上传者: 标签>Special JudgeICPC2026

[JAG 2026 Summer Camp #2] Edge Exchanges

题目描述

给定两棵树 AA 和 BB,每棵树都有 NN 个顶点。两棵树具有相同的带标号顶点集 {1,2,…,N}\{1,2,\ldots,N\}。

对于每个 ii(1≤i≤N−11\le i\le N-1),AA 的第 ii 条边连接顶点 uiu_i 和 viv_i。对于每个 jj(1≤j≤N−11\le j\le N-1),BB 的第 jj 条边连接顶点 xjx_j 和 yjy_j。

对于每个 i=1,2,…,N−1i=1,2,\ldots,N-1,解决以下问题。

找到一个满足 1≤j≤N−11\le j\le N-1 的整数 jj,使得进行下述交换后,AA 和 BB 仍然都是树:

  • 从 AA 中删除连接 uiu_i 和 viv_i 的边,从 BB 中删除连接 xjx_j 和 yjy_j 的边。
  • 然后在 AA 中添加连接 xjx_j 和 yjy_j 的边,在 BB 中添加连接 uiu_i 和 viv_i 的边。

每次交换独立考虑,均从原始的树 AA 和 BB 开始。

可以证明,在给定约束下,对于每个 ii,都至少存在一个满足要求的整数 jj。

输入格式

输入仅包含一组测试数据,格式如下。

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}

整数 NN 是 AA 和 BB 的顶点数(2≤N≤2×1052\le N\le 2\times 10^5)。

接下来的 N−1N-1 行描述 AA 的边。对于每个 i=1,…,N−1i=1,\ldots,N-1,整数 ui,viu_i,v_i(1≤ui,vi≤N1\le u_i,v_i\le N)表示第 ii 条边连接顶点 uiu_i 和 viv_i。保证 AA 是一棵树。

再接下来的 N−1N-1 行描述 BB 的边。对于每个 j=1,…,N−1j=1,\ldots,N-1,整数 xj,yjx_j,y_j(1≤xj,yj≤N1\le x_j,y_j\le N)表示第 jj 条边连接顶点 xjx_j 和 yjy_j。保证 BB 是一棵树。

输出格式

输出 N−1N-1 行。对于每个 i=1,2,…,N−1i=1,2,\ldots,N-1,第 ii 行应包含一个整数 jj,使其对于 AA 的第 ii 条边满足题目描述中的条件。

如果有多个合法答案,可以输出任意一个。

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

提示

样例输出的第一行对 i=1i=1 选择了 j=1j=1。将 AA 的边 (1,3)(1,3) 与 BB 的边 (1,2)(1,2) 交换后,AA 和 BB 仍然都是树。

对于 i=2i=2,AA 的边和所选的 BB 的边都是 (2,4)(2,4),因此交换它们不会改变任意一棵树。也可能存在其他合法输出。