#CW72. 双树连桥(bridge)

双树连桥(bridge)

题目描述

给定两棵结构完全相同的无向树 GG 和 HH。两棵树都包含编号为 11 到 nn 的顶点;如果 GG 中有边 (Gu,Gv)(G_u,G_v),那么 HH 中也有边 (Hu,Hv)(H_u,H_v),反之亦然。树中的叶子指度数为 11 的顶点。

对于每个叶子编号 xx,可以在 GxG_x 与 HxH_x 之间设置一条跨树连接。连接开启时,可以沿这条连接在 GxG_x 与 HxH_x 之间双向切换,切换不增加路径长度;连接关闭时,两点之间没有这条边。初始时所有叶子的连接都关闭。

需要处理以下两类操作:

  1. 操作 1 v:切换编号为 vv 的叶子的连接状态;
  2. 操作 2 u v:询问从 GuG_u 到 HvH_v 的最短路径长度。

路径长度只计算两棵树内部经过的树边数,跨树连接只用于从一棵树切换到另一棵树且长度为 00。因为起点在 GG、终点在 HH,一条可行路径至少要使用一条开启的跨树连接;如果当前没有开启的连接,答案为 −1-1。

输入格式

从 bridge.in 文件中读入。

第一行包含两个整数 n,qn,q,分别是每棵树的顶点数和操作数。接下来 n−1n-1 行,每行包含两个整数 u,vu,v,表示两棵树中对应的边 (Gu,Gv)(G_u,G_v) 和 (Hu,Hv)(H_u,H_v)。接下来 qq 行,每行是一条操作:

  1. 1 v 表示切换叶子 vv 的连接状态;
  2. 2 u v 表示从 GuG_u 到 HvH_v 的最短路径长度。

输入保证第一类操作中的 vv 一定是叶子,且给出的 n−1n-1 条边构成一棵树。

输出格式

向 bridge.out 文件中输出。

对于每条第二类操作输出一行一个整数,表示最短路径长度;若当前没有任何开启的跨树连接,则输出 −1-1。

样例 1 输入

7 11
1 2
2 3
1 4
2 5
4 6
4 7
1 6
1 3
2 1 6
2 1 2
1 7
2 5 4
2 6 3
1 6
1 3
1 5
2 6 3

样例 1 输出

2
3
5
4
6

样例 2 输入

3 2
1 2
1 3
1 3
2 1 2

样例 2 输出

3

样例 2 解释

树是一条 2−1−32-1-3 的路径,叶子为 22 和 33。开启叶子 33 的连接后,从 G1G_1 到 H2H_2 的走法是 G1→G3G_1\to G_3(11 步)、G3→H3G_3\to H_3(00 步)、H3→H1→H2H_3\to H_1\to H_2(22 步),共 33 步。

数据范围

设 kk 为全部 qq 次操作中第二类询问的数量。完整数据范围为 3≤n≤2×1053\le n\le 2\times 10^5、1≤q≤2×1051\le q\le 2\times 10^5、0≤k≤q0\le k\le q。每条边的两个端点和每个操作中的顶点编号都在 [1,n][1,n] 内;输入的 n−1n-1 条边保证构成一棵树,第一类操作只切换叶子。

本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。

子任务 分值 测试点 附加条件
1 3 11 n≤16n\le 16,q≤16q\le 16
2 2∼32\sim 3 n≤16n\le 16,q≤200000q\le 200000
3 2 44 n≤2000n\le 2000,q≤200000q\le 200000 且 k≤5k\le 5
4 8 55 n≤2000n\le 2000,q≤2000q\le 2000
5 9 66 n≤200000n\le 200000,q≤200000q\le 200000 且 k≤5k\le 5
6 30 7∼107\sim 10 所有第二类询问之后不再出现第一类操作
7 45 11∼2011\sim 20 完整约束