传送门

BZOJ100题辣（已经无法直视的正确率

树剖板子题，注意和dfs序结合，根据根的变化变换统计的方式即可。

//BZOJ 3083//by Cydiater//2016.10.23#include <iostream>#include <cstring>#include <string>#include <algorithm>#include <queue>#include <map>#include <ctime>#include <iomanip>#include <cstdlib>#include <cstdio>#include <cmath>using namespace std;#define ll long long#define up(i,j,n)		for(  int i=j;i<=n;i++)#define down(i,j,n)		for(int i=j;i>=n;i--)#define FILE "bbbbb"const int MAXN=1e5+5;const ll oo=1LL<<32;inline ll read(){	char ch=getchar();ll x=0,f=1;	while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}	while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}	return x*f;}int N,M,dep[MAXN],LINK[MAXN],len=0,fa[MAXN][25],son[MAXN],siz[MAXN],top[MAXN],seg[MAXN],cnt=0,pos[MAXN],ROOT,opt,L,R;ll v,pro[MAXN];int c=0;struct edge{	int y,next;}e[MAXN<<1];struct Tree{	ll v,delta;}t[MAXN<<3];namespace solution{	inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;}	inline void reload(int root){t[root].v=min(t[root<<1].v,t[root<<1|1].v);}	inline void downit(int root){		if(t[root].delta==0)return;		int delta=t[root].delta;t[root].delta=0;		t[root<<1].delta=delta;t[root<<1].v=delta;		t[root<<1|1].delta=delta;t[root<<1|1].v=delta;	}	void init(){		N=read();M=read();		up(i,2,N){			int x=read(),y=read();			insert(x,y);			insert(y,x);		}		up(i,1,N)pro[i]=read();		ROOT=read();	}	void dfs1(int node,int deep,int father){		fa[node][0]=father;dep[node]=deep;son[node]=0;		siz[node]=1;int max_siz=0;		for(int i=LINK[node];i;i=e[i].next)if(e[i].y!=father){			dfs1(e[i].y,deep+1,node);			siz[node]+=siz[e[i].y];			if(siz[e[i].y]>max_siz){				max_siz=siz[e[i].y];				son[node]=e[i].y;			}		}	}	void dfs2(int node,int TOP){		top[node]=TOP;seg[++cnt]=node;pos[node]=cnt;		if(son[node])dfs2(son[node],TOP);		for(int i=LINK[node];i;i=e[i].next)if(e[i].y!=fa[node][0]&&e[i].y!=son[node])			dfs2(e[i].y,e[i].y);	}	void get_ancestor(){		up(i,1,21)up(node,1,N)if(fa[node][i-1]!=0)			fa[node][i]=fa[fa[node][i-1]][i-1];	}	void build(int leftt,int rightt,int root){		if(leftt==rightt){			t[root].delta=0;			t[root].v=pro[seg[leftt]];			return;		}		int mid=(leftt+rightt)>>1;		build(leftt,mid,root<<1);		build(mid+1,rightt,root<<1|1);		reload(root);	}	void Build(){		dfs1(ROOT,0,0);dfs2(ROOT,ROOT);		get_ancestor();		build(1,N,1);	}	int LCA(int x,int y){		if(x==y)	return x;		if(dep[x]<dep[y])swap(x,y);		down(i,21,0)if(dep[x]-(1<<i)>=dep[y])x=fa[x][i];		if(x==y)	return x;		down(i,21,0)if(fa[x][i]!=0&&fa[x][i]!=fa[y][i]){			x=fa[x][i];			y=fa[y][i];		}		return fa[x][0];	}	void updata(int leftt,int rightt,int root){		downit(root);		if(leftt>R||rightt<L)	return;		if(leftt>=L&&rightt<=R){			t[root].delta=t[root].v=v;			return;		}		int mid=(leftt+rightt)>>1;		updata(leftt,mid,root<<1);		updata(mid+1,rightt,root<<1|1);		reload(root);	}	void change(int x,int aim){		while(top[x]!=top[aim]){			R=pos[x];L=pos[top[x]];			updata(1,N,1);			x=fa[top[x]][0];		}		R=pos[x];L=pos[aim];		updata(1,N,1);	}	void Change(int x,int y){		int lca=LCA(x,y);		change(x,lca);change(y,lca);	}	ll get(int leftt,int rightt,int root){		downit(root);		if(leftt>R||rightt<L)		return oo;		if(leftt>=L&&rightt<=R)		return t[root].v;		int mid=(leftt+rightt)>>1;		return min(get(leftt,mid,root<<1),get(mid+1,rightt,root<<1|1));	}	void slove(){		while(M--){			opt=read();			if(opt==1)ROOT=read();			else if(opt==2){				int x=read(),y=read();v=read();				Change(x,y);			}else{				int node=read(),Pos=pos[ROOT];ll ans;				int leftt=pos[node],rightt=leftt+siz[node]-1;				if(Pos==leftt){					L=1;R=N;					ans=get(1,N,1);				}else if(!(Pos>=leftt&&Pos<=rightt)){					L=leftt;R=rightt;					ans=get(1,N,1);				}else{					for(int i=LINK[node];i;i=e[i].next)if(e[i].y!=fa[node][0]){						leftt=pos[e[i].y];rightt=pos[e[i].y]+siz[e[i].y]-1;						if(Pos>=leftt&&Pos<=rightt){							L=1;R=leftt-1;							if(R>=L)ans=get(1,N,1);							L=rightt+1,R=N;							if(L<=R)ans=min(ans,get(1,N,1));							break;						}					}				}				printf("%lld\n",ans);			}		}	}}int main(){	//freopen(FILE".in","r",stdin);	//freopen(FILE".out","w",stdout);	//freopen("input.in","r",stdin);	//freopen("out.out","w",stdout);	using namespace solution;	init();	Build();	slove();	return 0;}

BZOJ3083: 遥远的国度