luogu3979/bzoj3083--遥远的国度
题目描述
zcwwzdjn在追杀十分sb的zhx，而zhx逃入了一个遥远的国度。当zcwwzdjn准备进入遥远的国度继续追杀时，守护神RapiD阻拦了zcwwzdjn的去路，他需要zcwwzdjn完成任务后才能进入遥远的国度继续追杀。
问题是这样的：遥远的国度有n个城市，这些城市之间由一些路连接且这些城市构成了一颗树。这个国度有一个首都，我们可以把这个首都看做整棵树的根，但遥远的国度比较奇怪，首都是随时有可能变为另外一个城市的。遥远的国度的每个城市有一个防御值，有些时候RapiD会使得某两个城市之间的路径上的所有城市的防御值都变为某个值。RapiD想知道在某个时候，如果把首都看做整棵树的根的话，那么以某个城市为根的子树的所有城市的防御值最小是多少。由于RapiD无法解决这个问题，所以他拦住了zcwwzdjn希望他能帮忙。但zcwwzdjn还要追杀sb的zhx，所以这个重大的问题就被转交到了你的手上。
题目大意
三种操作：变根，路径修改，查询子树中点权最小。
题解
非常明显，是一道树链剖分的模板题。
之后跟上算法xio小讲堂的地址（应该是第4讲）。
对于树链剖分，个人的理解就是将一棵树通过重轻的性质，展开到一个一维数组上，然后再通过各种数据结构来优化，比如说是线段树，并且我们树上的各个条链上的节点，在一维上的点是连续的，这样保证修改查询的顺序的可行性。
一个常识：在树链剖分中展开的一维数组中，原树上的节点\(u\)的范围是\(idx[u]\)~\(idx[u]+sz[u]-1\)，其中\(idx\)表示原来节点现在的编号，\(sz\)表示以\(u\)为根的子树的节点数。（为什么是这样我会在第4期的xio讲堂里讲解）
对于这一道题，除了一般的路径修改还有改变根节点的操作。
我们将这个根节点的操作简单化。
如果我们要求\(x\)节点为根的最小节点，整棵树的根节点是\(root\)。
如果\(x=root\)，显而易见，我们访问节点的答案就是整棵树的最小值。
如果\(lca(x,root)!=x\)，也就是x和root是在两个不同的链上，那么我们的答案也就是原来的\(x\)的子树的答案。
那么最后一种情况就是\(lca(x,root)=x\)，那么也就是说\(x\)成为了当前我们根节点的祖先。
这个玩意比较麻烦，但是画一张图，自己仔细观察一下，可以发现：我们要求的答案就是在\(root\)所在\(u\)的子树这条链以外的的所有其他子树。
那么我们就需要通过在一维数组中展开的树上的性质，枚举\(u\)节点的所有子节点，如果有一个节点深度比\(root\)，而且\(idx+sz-1\)≥root的编号，也就是说我们root就在\(v\)（当前访问\(u\)号节点）的子树内，那么我们就可以直接算答案了。
\(ps\).求这道题的\(lca\)可以是用倍增也可以用暴力求解，其实差不多的。
ac代码
#include<bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof(a))
#define inf 2100000000
#define N 1000005
using namespace std;
struct edge{
int to,nt;
}E[N<<1];
int cnt,n,m,tot,rt;
int H[N],sz[N],top[N],dep[N],fa[N],son[N],idx[N],val[N],a[N];
int read(){
int w=0,x=0;char ch=0;
while(!isdigit(ch))w|=ch=='-',ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return w?-x:x;
}
void addedge(int u,int v){
E[++cnt]=(edge){v,H[u]}; H[u]=cnt;
E[++cnt]=(edge){u,H[v]}; H[v]=cnt;
}
struct segment_tree{
#define lson (nod<<1)
#define rson (nod<<1|1)
#define mid (l+r>>1)
int tr[N<<2],lazy[N<<2];
void pushup(int nod){tr[nod]=min(tr[lson],tr[rson]);}
void pushdown(int nod){
if(lazy[nod]==-1) return;
tr[lson]=tr[rson]=lazy[nod];
lazy[lson]=lazy[rson]=lazy[nod];
lazy[nod]=-1;
}
void build(int l,int r,int nod,int *a){
lazy[nod]=-1;
if(l==r){
tr[nod]=a[l];
return;
}
build(l,mid,lson,a);
build(mid+1,r,rson,a);
pushup(nod);
}
void update(int l,int r,int ql,int qr,int v,int nod){
if(ql<=l&&r<=qr){
tr[nod]=v;
lazy[nod]=v;
return;
}
pushdown(nod);
if(ql<=mid) update(l,mid,ql,qr,v,lson);
if(qr>mid) update(mid+1,r,ql,qr,v,rson);
pushup(nod);
}
int query(int l,int r,int ql,int qr,int nod){
if(ql>r||qr<l) return inf;
if(ql<=l&&r<=qr) return tr[nod];
pushdown(nod);
int res=inf;
res=min(res,query(l,mid,ql,qr,lson));
res=min(res,query(mid+1,r,ql,qr,rson));
return res;
}
}T;
void dfs1(int u,int ft,int dp){
sz[u]=1;
fa[u]=ft;
dep[u]=dp;
int maxson=-1;
for(int e=H[u];e;e=E[e].nt){
int v=E[e].to;
if(v==fa[u]) continue;
dfs1(v,u,dp+1);
sz[u]+=sz[v];
if(sz[v]>maxson) maxson=sz[v],son[u]=v;
}
}
void dfs2(int u,int tp){
top[u]=tp;
idx[u]=++tot;
val[tot]=a[u];
if(!son[u]) return;
dfs2(son[u],tp);
for(int e=H[u];e;e=E[e].nt){
int v=E[e].to;
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
void Update(int a,int b,int v){//修改树上路径
while(top[a]!=top[b]){
if(dep[top[a]]<dep[top[b]]) swap(a,b);
T.update(1,n,idx[top[a]],idx[a],v,1);
a=fa[top[a]];
}
if(dep[a]>dep[b]) swap(a,b);
T.update(1,n,idx[a],idx[b],v,1);
}
int Lca(int x,int y){//求lca
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
return dep[x]<=dep[y]?x:y;
}
int Query(int u){
if(u==rt) return T.tr[1];
int lca=Lca(u,rt);
if(lca!=u) return T.query(1,n,idx[u],idx[u]+sz[u]-1,1);
int y;
for(int e=H[u];e;e=E[e].nt){
int v=E[e].to;
if(idx[v]<=idx[rt]&&idx[v]+sz[v]-1>=idx[rt]){y=v;break;}//找到root所在子树
}
int res=T.query(1,n,1,idx[y]-1,1); res=min(res,T.query(1,n,idx[y]+sz[y],n,1));
return res;
}
int main(){
tot=0,cnt=0;
n=read(),m=read();
for(int i=1;i<n;i++) addedge(read(),read());
for(int i=1;i<=n;i++) a[i]=read();
rt=read();
dfs1(1,-1,1); dfs2(1,1);
T.build(1,n,1,val);
while(m--){
int opt=read();
if(opt==1) rt=read();
if(opt==2){
int a=read(),b=read(),c=read();
Update(a,b,c);
}
if(opt==3){
int x=read();
printf("%d\n",Query(x));
}
}
return 0;
}