浅谈树链剖分 "换根操作"

$$\text{前言}$$

$\quad$最近在你谷上做了几道"换根操作"的树链剖分题，觉得有必要记录一下，以免以后忘记了。(如果没有见过这种题的可以去做做[P3979 遥远的国度](https://www.luogu.com.cn/problem/P3979)和[CF916E Jamie and Tree](https://www.luogu.com.cn/problem/CF916E))

$$\text{关于题目要求的操作}$$

$\quad$相信你已经看过这两道题了(~~没看过也没有没关系~~)，其实可以发现在一棵树中，只有父亲(祖先)，子树，深度，会因为根节点的变化而变化，所以题目一般需要你有换根操作，子树修改操作，求 $LCA$ (最近公共祖先)，我们分别来考虑一下。(可以看看下面这张图来理解，题目中的图)

![](https://cdn.luogu.com.cn/upload/image_hosting/gmu2iblr.png))

$$\text{换根}$$

$\quad$因为每换一次根，树中的很多信息都会改变，不可能每次换根都跑两便 $dfs$ 预处理，所以我们考虑其他方法，对于单纯的换根操作，只需要设置一个全局变量 $root$ 来存储根的编号( $root$ 初始化为 $1$ ，默认以 $1$ 为根)，对于其他操作，再通过分类讨论 $root$ 的位置来进行操作。

$$\text{LCA(最近公共祖先)}$$

$\quad$因为这题我们肯定用树链剖分解题，所以对于原图( $root==1$ )的情况下 $LCA$ 的求法肯定是使用树链剖分的(~~当然如果读者愿意专门打个倍增，那么你们随意~~)

$\quad$**注意：(小写) $lca(x,y)$ 表示在以1为根的树中 $x$ 和 $y$ 的最近公共祖先，(大写) $LCA(x,y)$ 表示在以 $root$ 为根的树中 $x$ 和 $y$ 的最近公共祖先。**

```cpp
il int lca(int x,int y) //模板树链剖分求LCA
{
  int fx=top[x],fy=top[y];
  while(fx!=fy)
    {
      if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
      x=father[fx];fx=top[x];
    }
  if(dep[x]>dep[y])swap(x,y);
  return x;
}
```

$\quad$接下来我们就要对 $root$ 的位置进行分类讨论了，代码先贴出来给你们看看。

```cpp
il int LCA(int x,int y)
{
  if(dep[x]>dep[y])swap(x,y);
  int xr=lca(x,root),yr=lca(y,root),xy=lca(x,y);
  if(xy==x)
  {
  	if(xr==x){if(yr==y)return y;return yr;}
  	return x;
  }
  if(xr==x)return x;if(yr==y)return y;
  if((xr==root&&xy==yr)||(yr==root&&xy==xr))return root;
  if(xr==yr)return xy;
  if(xy!=xr)return xr;return yr;
}
```

$\quad$另外我们可以再画几张图来方便理解。

一.当 $lca(x,y)==x$ (可以先按深度调序， $dep[x]<=dep[y]$)
 
   ![](https://cdn.luogu.com.cn/upload/image_hosting/hk78elxs.png)
$\quad$ $1$. 情况 $1$ ：$root$ 在 $x$ 的子树中，也在 $y$ 的子树中，即 $lca(x,root)==x$ && $lca(y,root)==y$ ，此时 $LCA(x,y)$ 是 $y$ ，因为图要反过来看(以 $root$ 为根)

$\quad$ $2$. 情况 $2$ ： $root$ 在 $x$ 的子树中，但不在 $y$ 的子树中，即 $lca(x,root)$ ，此时 $LCA(x,y)$ 是 $lca(y,root)$。

$\quad$ $3$. 情况 $3$ ：其他情况下， $LCA(x,y)$ 就是 $x$ 。

二.当 $lca(x,y)!=x$ (因为 $dep[x]<=dep[y]$，所以 $lca(x,y)!=y$ ， $x$ , $y$ 在不同子树上)

![](https://cdn.luogu.com.cn/upload/image_hosting/jg4eo3ji.png)

$\quad$ 1. 情况1：( $lca(x,root)==x$ )||( $lca(x,root)==x$ ),root在x(或y)的子树中时， $LCA(x,y)$ 为 $x$ (或 $y$ )，显然。

$\quad$ 2. 情况2：( $lca(x,root)==root$ && $lca(x,y)==lca(y,root)$ )||( $lca(y,root)==root$ && $lca(x,y)==lca(x,root)$)，即 $root$ 在 $x$ 到 $y$ 的简单路径上时，答案为 $root$ 。(也可以用深度判断， ( $lca(x,root)===root$ && $dep[root]>=dep[lca(x,y)]$ )||( $lca(y,root)==root$ && $dep[root]>=dep[lca(x,y)]$ ))

$\quad$ 3. 情况3： $lca(x,root)==lca(y,root)$ ，即 $root$ 在上方时，$LCA(x,y)$ 为 $lca(x,y)$ 。

$\quad$ 4. 情况4：当 $root$ 在$x$，$y$ 的链上节点的子树中时， $LCA(x,y)$ 为那个链上节点。

$\quad$这样就把树上所有 $root$ 位置的情况都考虑到了，不重不漏。

$$\text{子树修改(查询)}$$

![](https://cdn.luogu.com.cn/upload/image_hosting/4ar4m3w5.png)

$\quad$ 情况 $1$ ：当 $x=root$ 时， $x$ 就是此时整棵树的根，那么就是全局修改(查询)。

$\quad$ 情况 $2$ ：当 $root$ 在x子树中时，就需要特别判断了，根据图像我们可以发现此时x的真正子树是包括除了 $root$ 方向上的子树之外其他所有节点。

$\quad$ 情况 $3$ ：其他情况下 $x$ 的子树以 $root$ 为根和以 $1$ 为根是一样的。

$\quad$ 以上就是关于树链剖分 "换根操作" 笔记的全部内容了，如果喜欢，不妨点个赞吧！

正在渲染内容...