T543880 换根 LCA

你需要对给定的有根树（初始时根节点为 $1$）执行如下操作： - `1 x` 将根节点设为 $x$ - `2 x y` 求 $x,y$ 的树上最近公共祖先

第一行两个整数 $n,q$，分别表示节点数量和操作数 随后 $n-1$ 行，每行两个数 $x,y$，描述树上的一条边 $e_i$ 随后 $q$ 行，每行一个操作，格式如上

对每个 $2$ 操作输出答案

$20$% 数据满足 $n,q\le 100$ $30$% 数据满足 $n,q\le 5\times 10^3$ $35$% 数据满足 $n,q\le 5\times 10^4$ 另有 $10$% 数据满足 $\forall i\in[1,n-1],e_i=(i,i+1)$ 另有 $10$% 数据满足 $\forall i\in[1,n-1],e_i=(1,i+1)$ $100$% 数据满足 $n\le 2\times 10^5,q\le 4\times 10^5$，至少含有一个 $2$ 操作 _Author&Data: HaneDaniko_