bzoj 3083 树链剖分，换根
对于一颗树有以下操作
1.确定x为根，2.将u到v的简单路径上的数全改成c，3.询问当前以x为根的子树中的节点最小权值。
如果没有操作1：树链剖分很明显。
于是考虑换根对结果的影响：
Case 1：root=x 结果是全树最小值。
Case 2: root!=x且lca(root,x)=x 利用倍增求出x的孩子中是root祖先的那一个设为y，结果是全树除子树y以外最小值。
Case 3：lca(root,x)!=x 结果无影响，即子树x的最小值。
简述：树链剖分&lca/倍增
#include<bits/stdc++.h>
using namespace std;
const int inf=;
struct tr{int dep,sz,hs,tp,ls,rs,fa[];}t[];
struct st{int mn,tg;}seg[];
vector<int>g[];
int n,m,ans,rt,tt,v[],ps[];
void dfs1(int x,int p,int d)
{
t[x].fa[]=p;t[x].dep=d;t[x].hs=;t[x].sz=;
for(int i=;i<=;i++)if(t[x].dep>=<<i)t[x].fa[i]=t[t[x].fa[i-]].fa[i-];
for(int i=;i<g[x].size();i++)if(g[x][i]!=p)
{
dfs1(g[x][i],x,d+);
if(t[t[x].hs].sz<t[g[x][i]].sz)t[x].hs=g[x][i];
}
}
void dfs2(int x,int p)
{
t[x].tp=p;t[x].ls=ps[x]=++tt;
if(t[x].hs)dfs2(t[x].hs,p);
for(int i=;i<g[x].size();i++)if(g[x][i]!=t[x].fa[]&&g[x][i]!=t[x].hs)dfs2(g[x][i],g[x][i]);
t[x].rs=tt;
}
void up(int x){seg[x].mn=min(seg[x<<].mn,seg[x<<|].mn);}
void down(int x){seg[x<<]=seg[x<<|]=seg[x];seg[x].tg=;}
void build(int x,int l,int r)
{
if(l==r){seg[x].mn=v[l];return;}
int md=l+r>>;build(x<<,l,md);build(x<<|,md+,r);up(x);
}
void upd(int x,int l,int r,int tl,int tr,int c)
{
if(tl<=l&&r<=tr){seg[x]=(st){c,c};return;}
if(seg[x].tg)down(x);
int md=l+r>>;
if(tl<=md)upd(x<<,l,md,tl,tr,c);
if(tr>md)upd(x<<|,md+,r,tl,tr,c);
up(x);
}
void qry(int x,int l,int r,int tl,int tr)
{
if(tl<=l&&r<=tr){ans=min(ans,seg[x].mn);return;}
if(seg[x].tg)down(x);
int md=l+r>>;
if(tl<=md)qry(x<<,l,md,tl,tr);
if(tr>md)qry(x<<|,md+,r,tl,tr);
}
int gtlca(int x,int y)
{
if(t[x].dep<t[y].dep)swap(x,y);
int sub=t[x].dep-t[y].dep;
for(int i=;i<=;i++)if(sub&(<<i))x=t[x].fa[i];
for(int i=;i>=;i--)if(t[x].fa[i]!=t[y].fa[i])x=t[x].fa[i],y=t[y].fa[i];
if(x==y)return x;else return t[x].fa[];
}
int gtanc(int x,int d){for(int i=;i<=;i++)if(d&(<<i))x=t[x].fa[i];return x;}
void modify(int x,int y,int c)
{
int f1=t[x].tp,f2=t[y].tp;
while(f1!=f2)
{
if(t[f1].dep<t[f2].dep){swap(f1,f2);swap(x,y);}
upd(,,n,ps[f1],ps[x],c);
x=t[f1].fa[];f1=t[x].tp;
}
if(t[x].dep>t[y].dep)swap(x,y);
upd(,,n,ps[x],ps[y],c);
}
void query(int x)
{
int lca,v;
lca=gtlca(rt,x);
if(rt==x)printf("%d\n",seg[].mn);
else
{
ans=inf;
if(lca!=x)qry(,,n,t[x].ls,t[x].rs);
else
{
v=gtanc(rt,t[rt].dep-t[x].dep-);
if(t[v].ls>)qry(,,n,,t[v].ls-);
if(t[v].rs<n)qry(,,n,t[v].rs+,n);
}
printf("%d\n",ans);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<n;i++){int u,v;scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}
dfs1(,,);
dfs2(,);
for(int i=;i<=n;i++)scanf("%d",&v[ps[i]]);
build(,,n);
scanf("%d",&rt);
for(int i=;i<=m;i++)
{
int kd,x,y,c;scanf("%d",&kd);
if(kd==)scanf("%d",&rt);
else if(kd==){scanf("%d%d%d",&x,&y,&c);modify(x,y,c);}
else if(kd==){scanf("%d",&x);query(x);}
}
return ;
}