当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器：

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6723：wls 的树

题目描述
wls有一棵有根树，其中的点从$1$到$n$标号，其中$1$是树根。每次wls可以执行两种操作中的一个：

（1）选定一个点$x$，将以$x$为根的子树变成一条按照编号排序的链，其中编号最大的作为新的子树的根（成为原来$x$的父亲节点的儿子，如果原来$x$没有父亲节点则新的子树的根也没有父亲节点）。

（2）查询两个点之间的最短路径上经过了多少边。
输入解释
第一行一个整数$t$表示数据组数（$t\le10$）。

每组数据第一行一个正整数$n$表示树上的点数（$1\le n\le 100000$）。

接下来$n-1$行每行两个$1$到$n$之间的正整数表示一条树边。

接下来一行一个正整数$q$表示询问的个数（$1\le q\le 200000$）。

接下来$q$行每行表示一个操作。第一种操作格式为$1\ x$，其中$x$为指定的树根。第二种操作格式为$2\ x\ y$，表示查询从$x$到$y$的路径。
输出解释
对于每个第二种操作，输出一行一个正整数表示答案。
输入样例 
1
4
1 2
1 3
2 4
2
1 2
2 2 3
输出样例 
3
来自杭电HDUOJ的附加信息
Recommend liuyiding
该题目是Virtual Judge题目，来自 杭电HDUOJ
题目来源 2019 年百度之星·程序设计大赛 - 初赛四
源链接： HDU-6723
最后修改于 2020-10-25T23:33:49+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
时间上限 内存上限
6000/3000MS(Java/Others) 131072/131072K(Java/Others)