处理带换根操作的树链剖分（luogu P3979 遥远的国度）
这道题如果不考虑换根操作，当然就是一道裸的树链剖分。
那么直接考虑对于换根，怎么处理。
换一个根就重新剖一次当然是不现实的。
不妨就先以 1 号节点为根剖一下。
树链修改值当然直接按照重链在线段树上改就好了。
主要就是询问 x 子树最小值在对于不同的根时的各种状况。
那么设当前的根是 root 。
①： x==root ：当然就是全局最小值，直接输出。
②： x 是 root 在以 1 为根情况下的子树： root 为根或是 1 为根对 x 子树来说都一样，所以也直接按照正常操作查询就好了。
③： x 不属于以上情况，但也不在 1 到 root 的链上，在其他的支叉上： root 为根或是 1 为根还是没有影响，也直接查询。
④： x 在 1 到 root 的链上：这就是要处理的重点了。
怎么处理先放一放，先思考对于这几种情况，如何判断：
① x==root 当然好判断，②③本质是一样的，只要判断是不是情况④即可。
有多种方法，我是利用了树上倍增的方法。首先 x 在 1 到 root 的链上，必然有深度 d[x]<d[root] ，那么当 x 是root的祖先时， x 就必然是在 1 到 root 的链上了，那么即可判断 root 的 d[root]-d[x] 倍祖先，是不是 x ，这里我们维护一个倍增求 LCA 里用到的那种 2 的幂次倍增维护的祖先，每次查询祖先用倍增来查询就好了。
判断好了，剩下的就是处理了，我来画一个丑图：
图中蓝色的标号就是根据轻重链剖分进行的树上节点再标号 id ，红色笔迹标出的每一条树链就是一条重链，可以根据这个图来感性理解一下 x 不在 1 到 root 链上时的那种情况为什么可以直接查询。
上图中紫色圈出的节点即是当前 root ，绿色圈出的节点即是要查询的子树的根 x ，那么可以看出当前 x 在 1 到 root 的链上。思考现在 x 的子树，其实就是除去 x 往 root 方向的那个子树外，所有的节点。那么具体的需要的节点的 id 要怎么找出来呢？我们可以先找到所有不需要的节点，然后去掉这些节点，就是需要的节点了。找到 root 的 d[root]-d[x]-1 倍祖先，也就是 root 所在的 x 的子树的根节点 y ，那么 id[y]~id[y]+siz[y]-1 （ siz[i] ：以 1 为根时，以 i 节点为根的子树的大小）那么 1~id[y]-1 是需要的节点， id[y]+siz[y]~n 也是需要的节点，两部分分别求一下最小值，最后合起来求最小值即可。
下边放上代码，注释中也更详细的写了过程。
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rg register
const int N=100010;
const ll inf=9000000000000000000;
int n,m,tot,hed[N],ver[N<<1],nex[N<<1],d[N],f[N][25],son[N],siz[N],tp[N],
cnt,id[N],root,T;
ll a[N],vid[N],lz[N<<2],mi[N<<2],p,q;
inline char gc()
{
static char buf[1000001],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2) ? EOF : *p1++;
}
template <class T> inline void re(T &x)
{
x=0;
char ch=gc();
while(ch<'0'||ch>'9') ch=gc();
while(ch>='0'&&ch<='9') x=x*10+(ch^48), ch=gc();
}
inline void add(int x,int y)
{
ver[++tot]=y; nex[tot]=hed[x]; hed[x]=tot;
}
void dfs1(int x)
{
rg int i,y,sonsiz=-1;
siz[x]=1;
for(i=1;i<=T;++i)//处理倍增数组
{
f[x][i]=f[f[x][i-1]][i-1];
if(!f[x][i]) break;
}
for(i=hed[x];i;i=nex[i])
{
y=ver[i];
if(siz[y]) continue;
f[y][0]=x;
d[y]=d[x]+1;
dfs1(y);
siz[x]+=siz[y];//处理父节点f[][0]，深度d，子树大小siz，重儿子son
if(siz[y]>sonsiz) sonsiz=siz[y], son[x]=y;
}
}
void dfs2(int x,int thtp)
{
tp[x]=thtp;//记录所在重链链顶
id[x]=++cnt;//记录再标号
vid[cnt]=a[x];//记录每个标号对应的值
if(!son[x]) return;
dfs2(son[x],thtp);//先处理重儿子
rg int i,y;
for(i=hed[x];i;i=nex[i])
{
y=ver[i];
if(y==f[x][0]||y==son[x]) continue;
dfs2(y,y);//每个轻儿子都是一个重链的链顶
}
}
inline void update(int rt)
{
mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);
}
void build(int l,int r,int rt)
{
if(l==r) {mi[rt]=vid[l]; return;}
int mid=(l+r)>>1;
build(l,mid,rt<<1); build(mid+1,r,rt<<1|1);
update(rt);
}
inline void pushdown(int rt)//线段树下推懒标记
{
mi[rt<<1]=mi[rt<<1|1]=lz[rt];
lz[rt<<1]=lz[rt<<1|1]=lz[rt];
lz[rt]=0;
}
void modify(int l,int r,int L,int R,int k,int rt)//线段树区间修改
{
if(R<l||r<L) return;
if(L<=l&&r<=R) {mi[rt]=k; lz[rt]=k; return;}
int mid=(l+r)>>1;
if(lz[rt]) pushdown(rt);
modify(l,mid,L,R,k,rt<<1); modify(mid+1,r,L,R,k,rt<<1|1);
update(rt);
}
ll query(int l,int r,int L,int R,int rt)//线段树区间查询最小值
{
if(R<l||r<L) return inf;
if(L<=l&&r<=R) return mi[rt];
int mid=(l+r)>>1;
if(lz[rt]) pushdown(rt);
return min(query(l,mid,L,R,rt<<1),query(mid+1,r,L,R,rt<<1|1));
}
inline void adl(int x,int y,int k)
{
while(tp[x]!=tp[y])
{
if(d[tp[x]]<d[tp[y]]) swap(x,y);//每次更新链顶深度大的
modify(1,n,id[tp[x]],id[x],k,1);//更新当前点到链顶
x=f[tp[x]][0];//跳到链顶的父亲
}
if(d[x]<d[y]) swap(x,y);
modify(1,n,id[y],id[x],k,1);//最后在一条重链上了，直接更新
}
inline int getfa(int x,int k)
{
for(rg int i=T;i>=0;--i)
if(k>=(1<<i))
x=f[x][i], k-=(1<<i);
return x;
}
int main()
{
rg int i,x,y,k,opt;
re(n); re(m);
T=(int)log2(n)+1;
for(i=1;i<n;++i)
{
re(x); re(y);
add(x,y); add(y,x);
}
for(i=1;i<=n;++i) re(a[i]);
d[1]=1;//直接以1为根跑树剖
dfs1(1);
dfs2(1,1);
re(root);//读入当前根
build(1,n,1);//建树
while(m--)
{
re(opt);
switch(opt)
{
case 1:
re(root);//读入新根
break;
case 2:
re(x); re(y); re(k);
adl(x,y,k);//链更改
break;
case 3:
re(x);
if(x==root) printf("%lld\n",mi[1]);//是当前根节点，直接输出全局最小值
else
if(d[x]<d[root]&&f[y=getfa(root,d[root]-d[x]-1)][0]==x)//如果x是root的祖先的话
{//先找到了root在的x的子树的那个根
p=query(1,n,1,id[y]-1,1);//1~id[y]的部分
if(id[y]+siz[y]<=n) q=query(1,n,id[y]+siz[y],n,1);//id[y]+siz[y]~n的部分
else q=inf;
printf("%lld\n",min(p,q));//取min
}
else//否则直接查询x子树
printf("%lld\n",query(1,n,id[x],id[x]+siz[x]-1,1));
break;
}
}
return 0;
}