可以很显而易见的看出，修改就是树链剖分，而询问就是在dfs出的线段树里查询最小值，但由于这道题会修改根节点，所以在查询的时候需判断x是否为root的祖先，如果不是就直接做，是的话应该查询从1-st[y]-1 ed[y]+1 -- n 的最小值，其中y是root的祖先，x的儿子
PS:好久没做题，线段树都查了好久QAQ，还是没查出错来，最后只能cheat一个程序了QAQ
CODE：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 100010
#define maxm 200020
typedef long long ll ;
struct edges{
int to,next;
}edge[maxm];
int next[maxn],l,n,m;
int addedge(int x,int y){
edge[++l]=(edges){y,next[x]};next[x]=l;
edge[++l]=(edges){x,next[y]};next[y]=l;
return 0;
}
ll _min(ll x,ll y){
if (x==0) return y;
if (y==0) return x;
return min(x,y);
}
int dep[maxn],fa[maxn],sum[maxn],ch[maxn],pre[maxn],pos[maxn],add[maxn],lef[maxn],righ[maxn];
int cl;
bool b[maxn];
int dfs(int u){
dep[u]=dep[fa[u]]+1;
sum[u]=1;b[u]=1;
for (int i=next[u];i;i=edge[i].next)
if (!b[edge[i].to]){
fa[edge[i].to]=u;
dfs(edge[i].to);
sum[u]+=sum[edge[i].to];
ch[u]=sum[edge[i].to]>sum[ch[u]]?edge[i].to:ch[u];
}
return 0;
}
int heavy(int u,bool bo){
cl++;
pos[add[cl]=u]=cl;
b[u]=1;lef[u]=cl;
if (bo) pre[u]=u;
else pre[u]=pre[fa[u]];
if (ch[u]) heavy(ch[u],0);
for (int i=next[u];i;i=edge[i].next)
if (!b[edge[i].to])
heavy(edge[i].to,1);
righ[u]=cl;
return 0;
}
struct TREE{
int l,r;ll x;bool lazy;
}t[maxn*8];
ll s[maxn];
int buildtree(int x,int l,int r){
t[x].l=l;t[x].r=r;
if (l==r) {t[x].x=s[add[l]];return 0;}
buildtree(x<<1,l,(l+r)>>1);
buildtree((x<<1)+1,((l+r)>>1)+1,r);
t[x].x=_min(t[x<<1].x,t[(x<<1)+1].x);
return 0;
}
int pushdown(int x){
if (t[x].lazy) {
t[x<<1].x=t[(x<<1)+1].x=t[x].x;
t[x<<1].lazy=t[(x<<1)+1].lazy=1;
t[x].lazy=0;
}
return 0;
}
ll cha(int x,int x1,int y1){
int l=t[x].l,r=t[x].r;
if (l>y1||r<x1) return 0;
if (l==r) return (t[x].x);
if (l>=x1&&r<=y1) return t[x].x;
pushdown(x);
return _min(cha(x<<1,x1,y1),cha((x<<1)+1,x1,y1));
}
int gai(int x,ll y,int x1,int y1){
int l=t[x].l,r=t[x].r;
if (l>y1||r<x1) return 0;
if (l==r) {t[x].x=y;return 0;}
if (l>=x1&&r<=y1) {t[x].lazy=1;t[x].x=y;return 0;}
pushdown(x);
gai(x<<1,y,x1,y1);gai((x<<1)+1,y,x1,y1);
t[x].x=_min(t[x<<1].x,t[(x<<1)+1].x);
return 0;
}
int change(int l,int r,ll x){
for (;;){
if (pre[l]==pre[r]) {
if (dep[l]>dep[r]) swap(l,r);
gai(1,x,pos[l],pos[r]);
return 0;
}else{
if (dep[pre[l]]<dep[pre[r]]) swap(l,r);
gai(1,x,pos[pre[l]],pos[l]);
l=fa[pre[l]];
}
}
return 0;
}
int root,tem;
bool check(int x){
int y=root;
while (fa[y]!=0){
if (fa[y]==x) {tem=y;return 1;}
if (dep[fa[y]]<dep[x]) return 0;
if (pre[fa[y]]==pre[x]) {tem=ch[x];return 1;}
y=pre[fa[y]];
}
return 0;
}
ll query(int x){
if (!check(x))return (cha(1,lef[x],righ[x]));
else return (_min(cha(1,1,lef[tem]-1),cha(1,righ[tem]+1,n)));
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<n;i++) {
int x,y;
scanf("%d%d",&x,&y);
addedge(x,y);
}
for (int i=1;i<=n;i++) scanf("%lld",s+i);
memset(b,0,sizeof(b));
dfs(1);
memset(b,0,sizeof(b));
heavy(1,1);
buildtree(1,1,n);
scanf("%d",&root);
while (m--){
int opt,l,r;ll x;
scanf("%d",&opt);
if (opt==1) scanf("%d",&root);
if (opt==2) {
scanf("%d%d%lld",&l,&r,&x);
change(l,r,x);
}
if (opt==3){
scanf("%d",&l);
printf("%lld
",query(l));
}
}
return 0;
}