#CW72. 双树连桥(bridge)
双树连桥(bridge)
题目描述
给定两棵结构完全相同的无向树 和 。两棵树都包含编号为 到 的顶点;如果 中有边 ,那么 中也有边 ,反之亦然。树中的叶子指度数为 的顶点。
对于每个叶子编号 ,可以在 与 之间设置一条跨树连接。连接开启时,可以沿这条连接在 与 之间双向切换,切换不增加路径长度;连接关闭时,两点之间没有这条边。初始时所有叶子的连接都关闭。
需要处理以下两类操作:
- 操作
1 v:切换编号为 的叶子的连接状态; - 操作
2 u v:询问从 到 的最短路径长度。
路径长度只计算两棵树内部经过的树边数,跨树连接只用于从一棵树切换到另一棵树且长度为 。因为起点在 、终点在 ,一条可行路径至少要使用一条开启的跨树连接;如果当前没有开启的连接,答案为 。
输入格式
从 bridge.in 文件中读入。
第一行包含两个整数 ,分别是每棵树的顶点数和操作数。接下来 行,每行包含两个整数 ,表示两棵树中对应的边 和 。接下来 行,每行是一条操作:
1 v表示切换叶子 的连接状态;2 u v表示从 到 的最短路径长度。
输入保证第一类操作中的 一定是叶子,且给出的 条边构成一棵树。
输出格式
向 bridge.out 文件中输出。
对于每条第二类操作输出一行一个整数,表示最短路径长度;若当前没有任何开启的跨树连接,则输出 。
样例 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 解释
树是一条 的路径,叶子为 和 。开启叶子 的连接后,从 到 的走法是 ( 步)、( 步)、( 步),共 步。
数据范围
设 为全部 次操作中第二类询问的数量。完整数据范围为 、、。每条边的两个端点和每个操作中的顶点编号都在 内;输入的 条边保证构成一棵树,第一类操作只切换叶子。
本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。
| 子任务 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| 1 | 3 | , | |
| 2 | , | ||
| 3 | 2 | , 且 | |
| 4 | 8 | , | |
| 5 | 9 | , 且 | |
| 6 | 30 | 所有第二类询问之后不再出现第一类操作 | |
| 7 | 45 | 完整约束 |