题意：给出一棵树，这棵树每个点有权值，然后有3种操作。操作一：修改树根为rt，操作二：修改u到v路径上点权值为w，操作三：询问以rt为根x子树的最小权值。
解法：如果没有修改树根操作那么这题就是树链剖分的裸题。但是修改树根操作会使得题目变得复杂一些，这里直接说结论：我们先直接以1为根建树进行树链剖分，这样的话根固定了那么路径修改操作就照常，然后我们要考虑换根操作对查询的影响（这是重点）。
画图分析后可以发现，可以分为3种情况，①x==rt，询问的就是整棵树 ②x不在1到rt的路径上，对查询没有影响，查询照常 3 x在1到rt的路径上，这样会麻烦一些，仔细观察图发现其实查询就变成了查询除去（x的rt所在的子树）那么我们就可以先用倍增找到（x的rt所在的子树）这颗子树的根为 y=rt的dep[rt]-dep[x]-1级祖先。这样查询除去y的子树剩下的左右两个区间合并就是答案了。
这道题还是很不错的，做了能涨处理这样的换根问题的姿势。
#include<bits/stdc++.h> using namespace std; typedef long long LL; const LL INF=1LL<<60; const int N=1e5+10; int n,m,T,rt,num=0,f[N][20]; LL v[N]; struct node{ int dep,fa,sz,heavy; int toseg,top; LL val; }tree[N]; //原本的树 int totree[N<<2]; //线段树点i代表原树的点totree[i] /*-------------------------以下为线段树-----------------------------*/ LL Min[N<<2],tag[N<<2]; void pushdown(int rt) { if (!tag[rt]) return; Min[rt<<1]=tag[rt<<1]=tag[rt]; Min[rt<<1|1]=tag[rt<<1|1]=tag[rt]; tag[rt]=0; } void pushup(int rt) { Min[rt]=min(Min[rt<<1],Min[rt<<1|1]); } void build(int rt,int l,int r) { if (l==r) { Min[rt]=tree[totree[l]].val; tag[rt]=0; return; } int mid=l+r>>1; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); pushup(rt); } void update(int rt,int l,int r,int ql,int qr,LL v) { if (ql<=l && r<=qr) { Min[rt]=tag[rt]=v; return; } int mid=l+r>>1; pushdown(rt); if (ql<=mid) update(rt<<1,l,mid,ql,qr,v); if (qr>mid) update(rt<<1|1,mid+1,r,ql,qr,v); pushup(rt); } LL query(int rt,int l,int r,int ql,int qr) { if (ql<=l && r<=qr) return Min[rt]; int mid=l+r>>1; LL ret=INF; pushdown(rt); if (ql<=mid) ret=min(ret,query(rt<<1,l,mid,ql,qr)); if (qr>mid) ret=min(ret,query(rt<<1|1,mid+1,r,ql,qr)); return ret; } /*--------------------------以下为树链剖分----------------------------*/ int cnt=1,head[N<<1],to[N<<1],nxt[N<<1]; void add_edge(int x,int y) { nxt[++cnt]=head[x]; to[cnt]=y; head[x]=cnt; } void dfs1(int x,int fa,int dep) { //点x的父亲为fa深度为dep tree[x].dep=dep; tree[x].fa=fa; tree[x].sz=1; tree[x].val=v[x]; int maxson=-1; for (int i=head[x];i;i=nxt[i]) { int y=to[i]; if (y==fa) continue; f[y][0]=x; //在dfs1的时候顺便求倍增数组 for (int j=1;j<=T;j++) f[y][j]=f[f[y][j-1]][j-1]; dfs1(y,x,dep+1); tree[x].sz+=tree[y].sz; if (tree[y].sz>maxson) tree[x].heavy=y,maxson=tree[y].sz; } } void dfs2(int x,int top) { //点x所在树链的top tree[x].toseg=++num; tree[x].top=top; totree[num]=x; if (!tree[x].heavy) return; //叶子结点 dfs2(tree[x].heavy,top); //先剖分重儿子 for (int i=head[x];i;i=nxt[i]) { //再剖分轻儿子 int y=to[i]; if (y==tree[x].fa || y==tree[x].heavy) continue; dfs2(y,y); } } void update2(int x,int y,LL z) { //修改x到y路径的值 while (tree[x].top!=tree[y].top) { //不在同一条链上 if (tree[tree[x].top].dep<tree[tree[y].top].dep) swap(x,y); //x为深度大的链 update(1,1,n,tree[tree[x].top].toseg,tree[x].toseg,z); //x向上跳的同时更新 x=tree[tree[x].top].fa; //深度大的向上跳 } if (tree[x].dep>tree[y].dep) swap(x,y); //这里x和y在同一条链 update(1,1,n,tree[x].toseg,tree[y].toseg,z); //x和y这条链的更新 } int getfa(int x,int k) { //取得x的k级祖先 if (k<0) return -1; for (int i=T;i>=0;i--) if (k>=(1<<i)) x=f[x][i],k-=(1<<i); return x; } int main() { cin>>n>>m; T=(int)log2(n)+1; for (int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); add_edge(x,y); add_edge(y,x); } for (int i=1;i<=n;i++) scanf("%lld",&v[i]); dfs1(1,0,1); dfs2(1,1); build(1,1,n); scanf("%d",&rt); for (int i=1;i<=m;i++) { LL opt,x,y,z; scanf("%lld",&opt); if (opt==1) { scanf("%d",&rt); } if (opt==2) { scanf("%lld%lld%lld",&x,&y,&z); update2(x,y,z); } if (opt==3) { scanf("%lld",&x); if (x==rt) printf("%lld\n",query(1,1,n,1,n)); //x就是root else if (x==getfa(rt,tree[rt].dep-tree[x].dep)) { //x在1到root的路径上 y=getfa(rt,tree[rt].dep-tree[x].dep-1); //取得去掉部分的根（这要画图理解） z=INF; if (tree[y].toseg-1>=1) z=min(z,query(1,1,n,1,tree[y].toseg-1)); if (tree[y].toseg+tree[y].sz<=n) z=min(z,query(1,1,n,tree[y].toseg+tree[y].sz,n)); printf("%lld\n",z); } else { //其他情况,直接查询子树 printf("%lld\n",query(1,1,n,tree[x].toseg,tree[x].toseg+tree[x].sz-1)); } } } return 0; }
原文：https://www.cnblogs.com/clno1/p/11175089.html