原文发表时间：2014-09-05
先暂时无视掉换根。如果只有树上路径操作的话就是树剖sb题，只有子树操作的话就是dfs序sb题。但是这题两者都有，怎么办呢？实际上，树剖的时候在同一个子树中的节点也是在一个连续的区间中的，就是说，树剖其实也是dfs序。那么后两个操作就解决了。
接着就是换根。画个图yy一下就能发现，换根并不会影响所有节点的子树。我们实现的时候不需要改变树的形态，先随便取一个点作为根，查询/修改时只要分以下三种情况讨论一下即可：
1、u就是root，那么就直接输出全部节点的min。
2、lca(u,root)不为u，那么u的子树没有改变，答案就是u的子树中的最小值。
3、lca(u,root)是u，假设v为u的儿子且root在v的子树内，答案就是u的子树的补集，即dfs序中的和。这里v直接用树剖往上跳就能在找到了。
时间复杂度。
另外这题似乎是不会爆32位无符号整型的……反正我直接用int也A了……
code
#include <cstdio>
#include <algorithm>
#define repu(i,x,y) for (i=x; i<=y; ++i)
#define repe(i,x) for (edge *i=first[x]; i; i=i->next)
#define lc now<<1
#define rc now<<1|1
#define mid ((l+r)>>1)
using namespace std;
int n,m,i,a[100100],u,v,w,root,s[100100],dep[100100],son[100100],fa[100100],top[100100],
cnt,l[100100],r[100100],ql,qr,minv[262144],tag[262144],type,ans;
struct edge
{
int v;
edge *next;
} pool[200100],*tp=pool,*first[100100];
void dfs(int x)
{
s[x]=1;
repe(i,x)
if (i->v!=fa[x])
{
fa[i->v]=x;
dep[i->v]=dep[x]+1;
dfs(i->v);
if (s[i->v]>s[son[x]])
son[x]=i->v;
s[x]+=s[i->v];
}
}
inline void push_down(int now)
{
if (!tag[now])
return;
minv[lc]=minv[rc]=tag[lc]=tag[rc]=tag[now];
tag[now]=0;
}
void modify(int now,int l,int r)
{
if (ql<=l && qr>=r)
{
minv[now]=tag[now]=w;
return;
}
push_down(now);
if (ql<=mid)
modify(lc,l,mid);
if (qr>mid)
modify(rc,mid+1,r);
minv[now]=min(minv[lc],minv[rc]);
}
void dfs_(int x)
{
ql=qr=l[x]=r[x]=++cnt,w=a[x],modify(1,1,n);
if (s[x]==1)
return;
top[son[x]]=top[x];
dfs_(son[x]);
repe(i,x)
if (i->v!=fa[x] && i->v!=son[x])
{
top[i->v]=i->v;
dfs_(i->v);
}
r[x]=cnt;
}
void query(int now,int l,int r)
{
if (ql<=l && qr>=r)
{
ans=min(ans,minv[now]);
return;
}
push_down(now);
if (ql<=mid)
query(lc,l,mid);
if (qr>mid)
query(rc,mid+1,r);
}
int lca(int u,int v)
{
while (top[u]!=top[v])
{
if (dep[top[u]]<dep[top[v]])
swap(u,v);
if (type==2)
ql=l[top[u]],qr=l[u],modify(1,1,n);
u=fa[top[u]];
}
if (dep[u]>dep[v])
swap(u,v);
if (type==2)
ql=l[u],qr=l[v],modify(1,1,n);
return u;
}
int query(int u,int v)
{
while (dep[fa[top[u]]]>dep[v])
u=fa[top[u]];
if (fa[top[u]]==v)
return top[u];
return son[v];
}
int main()
{
scanf("%d%d",&n,&m);
repu(i,1,n-1)
{
scanf("%d%d",&u,&v);
tp->v=v,tp->next=first[u],first[u]=tp++;
tp->v=u,tp->next=first[v],first[v]=tp++;
}
repu(i,1,n)
scanf("%d",&a[i]);
dfs(1);
dfs_(top[1]=1);
scanf("%d",&root);
while (m--)
{
scanf("%d",&type);
if (type==1)
scanf("%d",&root);
if (type==2)
{
scanf("%d%d%d",&u,&v,&w);
lca(u,v);
}
if (type==3)
{
scanf("%d",&u);
if (u==root)
printf("%d\n",minv[1]);
else
{
ans=2147483647;
if (lca(u,root)!=u)
ql=l[u],qr=r[u],query(1,1,n);
else
{
v=query(root,u);
if (l[v]>1)
ql=1,qr=l[v]-1,query(1,1,n);
if (r[v]<n)
ql=r[v]+1,qr=n,query(1,1,n);
}
printf("%d\n",ans);
}
}
}
return 0;
}
