目录

• 「学习笔记」树链剖分
  • 树链剖分
    • 算法
    • 实现
    • 例题
      • 思路
      • 代码
  • 练习题
    • 染色
      • 思路
      • 代码
    • QTREE
      • 思路
      • 代码
    • [HAOI2015]树上操作
      • 思路
      • 代码
    • [NOIP2013 提高组] 货车运输
      • 思路
      • 代码
    • [NOIP2015 提高组] 运输计划
      • 思路
      • 代码
    • 遥远的国度
      • 思路
      • 代码

const ll N=3e4+10,inf=1ll<<40;
ll n,q,w[N];
vector<ll>tu[N];
ll fa[N],dep[N],sz[N],son[N];//dfs1
ll cnt=0,top[N],dfn[N],rk[N];//dfs2
class SegmentTree{
public:
	class TREE{
	public:
		ll mx,va;
	}tr[N<<2];
	#define ls(p) (p<<1)
	#define rs(p) (p<<1|1)
	#define mx(p) tr[p].mx
	#define va(p) tr[p].va
	#define l_s(p) ls(p),l,mid
	#define r_s(p) rs(p),mid+1,r
	inline void Pushup(ll p){
		mx(p)=max(mx(ls(p)),mx(rs(p)));
		va(p)=va(ls(p))+va(rs(p));
	}
	void Build(ll p,ll l,ll r){
		if(l==r)mx(p)=va(p)=w[rk[l]];
		else{
			bdmd;
			Build(l_s(p));
			Build(r_s(p));
			Pushup(p);
		}
		return;
	}
	void Update(ll p,ll l,ll r,ll x,ll val){
		if(l>x||r<x)return;
		if(l==r)mx(p)=va(p)=val;
		else{
			bdmd;
			Update(l_s(p),x,val);
			Update(r_s(p),x,val);
			Pushup(p);
		}
		return;
	}
	ll QueryMax(ll p,ll l,ll r,ll le,ll ri){
		if(r<le||ri<l)return -inf;
		if(le<=l&&r<=ri)return mx(p);
		bdmd;
		return max(QueryMax(l_s(p),le,ri),QueryMax(r_s(p),le,ri));
	}
	ll QuerySum(ll p,ll l,ll r,ll le,ll ri){
		if(r<le||ri<l)return 0;
		if(le<=l&&r<=ri)return va(p);
		bdmd;
		return QuerySum(l_s(p),le,ri)+QuerySum(r_s(p),le,ri);
	}
}tr;
class KillTree{
public:
	void Dfs1(ll u){
		son[u]=-1,sz[u]=1;
		far(v,tu[u]){
			if(v==fa[u])continue;
			dep[v]=dep[u]+1,fa[v]=u;
			Dfs1(v);
			sz[u]+=sz[v];
			if(son[u]==-1||sz[v]>sz[son[u]])son[u]=v;
		}
		return;
	}
	void Dfs2(ll u,ll t){
		top[u]=t;
		dfn[u]=++cnt;
		rk[cnt]=u;
		if(son[u]==-1)return;
		Dfs2(son[u],t);
		far(v,tu[u])if(v!=fa[u]&&v!=son[u])Dfs2(v,v);
		return;
	}
	inline void Update(ll x,ll val){tr.Update(1,1,n,dfn[x],val);}
	inline ll QueryMax(ll x,ll y){
		ll num=-inf,tx=top[x],ty=top[y];
		while(tx!=ty){
			if(dep[tx]>=dep[ty])num=max(num,tr.QueryMax(1,1,n,dfn[tx],dfn[x])),x=fa[tx];
			else num=max(num,tr.QueryMax(1,1,n,dfn[ty],dfn[y])),y=fa[ty];
			tx=top[x],ty=top[y];
		}
		num=max(num,tr.QueryMax(1,1,n,min(dfn[x],dfn[y]),max(dfn[x],dfn[y])));
		return num;
	}
	inline ll QuerySum(ll x,ll y){
		ll num=0,tx=top[x],ty=top[y];
		while(tx!=ty){
			if(dep[tx]>=dep[ty])num+=tr.QuerySum(1,1,n,dfn[tx],dfn[x]),x=fa[tx];
			else num+=tr.QuerySum(1,1,n,dfn[ty],dfn[y]),y=fa[ty];
			tx=top[x],ty=top[y];
		}
		num+=tr.QuerySum(1,1,n,min(dfn[x],dfn[y]),max(dfn[x],dfn[y]));
		return num;
	}
}kt;
namespace SOLVE{
	inline ll rnt(){
		ll x=0,w=1;char c=getchar();
		while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
		while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
		return x*w;
	}
	inline void In(){
		n=rnt();
		_for(i,1,n-1){
			ll u=rnt(),v=rnt();
			tu[u].push_back(v);
			tu[v].push_back(u);
		}
		_for(i,1,n)w[i]=rnt();
		kt.Dfs1(1),kt.Dfs2(1,1),tr.Build(1,1,n);
		q=rnt();
		ll c=0;
		_for(i,1,q){
			char s[10];
			scanf("%s",s);
			ll x=rnt(),y=rnt();
			if(s[1]=='H')kt.Update(x,y);
			else if(s[1]=='M')printf("%lld\n",kt.QueryMax(x,y));
			else printf("%lld\n",kt.QuerySum(x,y));
		}
		return;
	}
}

const ll N=2e5+10,inf=1ll<<40;
ll n,q,co[N],k[N];
vector<ll>tu[N];
ll fa[N],dep[N],sz[N],son[N];//dfs1
ll cnt=0,top[N],dfn[N],rk[N];//dfs2
class KillTree{
public:
	class SegmentTree{
	public:
		class TREE{public:ll hd,tl,cnt,tag;}tr[N<<2];
		#define ls(p) (p<<1)
		#define rs(p) (p<<1|1)
		#define hd(p) tr[p].hd
		#define tl(p) tr[p].tl
		#define cn(p) tr[p].cnt
		#define ta(p) tr[p].tag
		#define l_s(p) ls(p),l,mid
		#define r_s(p) rs(p),mid+1,r
		inline void Pushup(ll p){
			hd(p)=hd(ls(p)),tl(p)=tl(rs(p));
			cn(p)=cn(ls(p))+cn(rs(p));
			if(tl(ls(p))==hd(rs(p)))--cn(p);
			return;
		}
		inline void Tag(ll p,ll color){
			cn(p)=1,ta(p)=color;
			hd(p)=color,tl(p)=color;
			return;
		}
		inline void Pushdown(ll p){
			if(ta(p)==-1)return;
			Tag(ls(p),ta(p));
			Tag(rs(p),ta(p));
			ta(p)=-1;
			return;
		}
		void Build(ll p,ll l,ll r){
			if(l==r)Tag(p,co[rk[l]]);
			else{
				bdmd;
				Build(l_s(p));
				Build(r_s(p));
				Pushup(p);
			}
			ta(p)=-1;
			return;
		}
		void Update(ll p,ll l,ll r,ll le,ll ri,ll color){
			if(ri<l||r<le)return;
			Pushdown(p);
			if(le<=l&&r<=ri)Tag(p,color);
			else{
				bdmd;
				Update(l_s(p),le,ri,color);
				Update(r_s(p),le,ri,color);
				Pushup(p);
			}
			return;
		}
		ll Query(ll p,ll l,ll r,ll le,ll ri){
			if(ri<l||r<le)return 0;
			Pushdown(p);
			if(le<=l&&r<=ri)return cn(p);
			else{
				bdmd;
				ll ans1=Query(l_s(p),le,ri);
				ll ans2=Query(r_s(p),le,ri);
				if(ans1>0&&ans2>0&&tl(ls(p))==hd(rs(p)))--ans1;
				return ans1+ans2;
			}
		}
		ll QueryP(ll p,ll l,ll r,ll x){
			if(x<l||r<x)return 0;
			Pushdown(p);
			if(l==r)return hd(p);
			else{
				bdmd;
				ll an=QueryP(l_s(p),x)+QueryP(r_s(p),x);
				return an;
			}
		}
	}tr;
	void Dfs1(ll u){
		sz[u]=1,son[u]=-1;
		far(v,tu[u]){
			if(v==fa[u])continue;
			fa[v]=u,dep[v]=dep[u]+1;
			Dfs1(v);
			sz[u]+=sz[v];
			if(son[u]==-1||sz[v]>sz[son[u]])son[u]=v;
		}
		return;
	}
	void Dfs2(ll u,ll t){
		top[u]=t;
		dfn[u]=++cnt;
		rk[cnt]=u;
		if(son[u]==-1)return;
		Dfs2(son[u],t);
		far(v,tu[u])if(v!=fa[u]&&v!=son[u])Dfs2(v,v);
		return;
	}
	inline void Build(){fa[1]=1,Dfs1(1),Dfs2(1,1),tr.Build(1,1,n);}
	inline void Update(ll x,ll y,ll color){
		ll tx=top[x],ty=top[y];
		while(tx!=ty){
			if(dep[tx]>=dep[ty])swap(x,y),swap(tx,ty);
			tr.Update(1,1,n,dfn[ty],dfn[y],color),y=fa[ty];
			tx=top[x],ty=top[y];
		}
		tr.Update(1,1,n,min(dfn[x],dfn[y]),max(dfn[x],dfn[y]),color);
	}
	inline ll Query(ll x,ll y){
		ll num=0,tx=top[x],ty=top[y];
		while(tx!=ty){
			if(dep[tx]>=dep[ty])swap(x,y),swap(tx,ty);
			num+=tr.Query(1,1,n,dfn[ty],dfn[y]),y=fa[ty];
			if(y&&tr.QueryP(1,1,n,dfn[ty])==tr.QueryP(1,1,n,dfn[y]))--num;
			tx=top[x],ty=top[y];
		}
		num+=tr.Query(1,1,n,min(dfn[x],dfn[y]),max(dfn[x],dfn[y]));
		return num;
	}
}kt;
namespace SOLVE{
	inline ll rnt(){
		ll x=0,w=1;char c=getchar();
		while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
		while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
		return x*w;
	}
	inline char rch(){
		char c=getchar();
		while(c<'A'||c>'Z')c=getchar();
		return c;
	}
	inline void In(){
		n=rnt(),q=rnt();
		_for(i,1,n)co[i]=rnt();
		_for(i,1,n-1){
			ll u=rnt(),v=rnt();
			tu[u].push_back(v);
			tu[v].push_back(u);
		}
		kt.Build();
		_for(i,1,q){
			char op=rch();
			if(op=='C'){
				ll a=rnt(),b=rnt(),op=rnt();
				kt.Update(a,b,op);
			}
			else{
				ll a=rnt(),b=rnt();
				printf("%lld\n",kt.Query(a,b));
			}
		}
		return;
	}
}

const ll N=2e4+10,inf=1ll<<40;
ll n,q,c[N],k[N];
class Edge{public:ll u,v,w;}e[N];
vector<pair<ll,ll> >tu[N];
ll fa[N],dep[N],sz[N],son[N];
ll cnt,top[N],dfn[N],rk[N];
class KillTree{
public:
	class SegmentTree{
	public:
		ll mx[N<<4];
		#define ls(p) (p<<1)
		#define rs(p) (p<<1|1)
		#define l_s(p) ls(p),l,mid
		#define r_s(p) rs(p),mid+1,r
		void Build(ll p,ll l,ll r){
			if(l==r)mx[p]=c[rk[l]];
			else{
				bdmd;
				Build(l_s(p)),Build(r_s(p));
				mx[p]=max(mx[ls(p)],mx[rs(p)]);
			}
			return;
		}
		void Update(ll p,ll l,ll r,ll x,ll val){
			if(r<x||x<l)return;
			if(l==r)mx[p]=val;
			else{
				bdmd;
				Update(l_s(p),x,val),Update(r_s(p),x,val);
				mx[p]=max(mx[ls(p)],mx[rs(p)]);
			}
			return;
		}
		ll Query(ll p,ll l,ll r,ll le,ll ri){
			if(r<le||ri<l)return -inf;
			if(le<=l&&r<=ri)return mx[p];
			else{
				bdmd;
				return max(Query(l_s(p),le,ri),Query(r_s(p),le,ri));
			}
		}
	}tr;
	void Dfs1(ll u){
		sz[u]=1,son[u]=-1;
		far(pr,tu[u]){
			ll v=pr.first;
			if(v==fa[u])continue;
			c[v]=pr.second;
			fa[v]=u,dep[v]=dep[u]+1;
			Dfs1(v);
			sz[u]+=sz[v];
			if(son[u]==-1||sz[son[u]]<sz[v])son[u]=v;
		}
		return;
	}
	void Dfs2(ll u,ll t){
		top[u]=t;
		dfn[u]=++cnt;
		rk[cnt]=u;
		if(son[u]==-1)return;
		Dfs2(son[u],t);
		far(pr,tu[u]){
			ll v=pr.first;
			if(v!=fa[u]&&v!=son[u])
				Dfs2(v,v);
		}
		return;
	}
	inline void Build(){Dfs1(1),Dfs2(1,1),tr.Build(1,1,n);}
	inline void Update(ll x,ll y,ll z){
		if(fa[y]==x)swap(x,y);
		tr.Update(1,1,n,dfn[x],z);
		return;
	}
	inline ll GetLCA(ll x,ll y){
		ll tx=top[x],ty=top[y];
		while(tx!=ty){
			if(dep[tx]>dep[ty])swap(x,y),swap(tx,ty);
			y=fa[ty],ty=top[y];
		}
		if(dep[x]>dep[y])swap(x,y);
		return x;
	}
	inline ll Query(ll x,ll y){
		ll lca=GetLCA(x,y),la=tr.Query(1,1,n,dfn[lca],dfn[lca]);
		tr.Update(1,1,n,dfn[lca],-inf);
		ll num=-inf,tx=top[x],ty=top[y];
		while(tx!=ty){
			if(dep[tx]>dep[ty])swap(x,y),swap(tx,ty);
			num=max(num,tr.Query(1,1,n,dfn[ty],dfn[y])),y=fa[ty],ty=top[y];
		}
		num=max(num,tr.Query(1,1,n,min(dfn[x],dfn[y]),max(dfn[x],dfn[y])));
		tr.Update(1,1,n,dfn[lca],la);
		return num;
	}
}kt;
namespace SOLVE{
	inline ll rnt(){
		ll x=0,w=1;char c=getchar();
		while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
		while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
		return x*w;
	}
	inline char rch(){
		char c=getchar();
		while(c<'A'||c>'Z')c=getchar();
		return c;
	}
	inline void Clear(){
		_for(i,1,n)tu[i].clear();
		memset(e,0,sizeof(e));
		memset(fa,0,sizeof(fa));
		memset(dep,0,sizeof(dep));
		memset(sz,0,sizeof(sz));
		memset(son,0,sizeof(son));
		memset(top,0,sizeof(top));
		memset(dfn,0,sizeof(dfn));
		memset(rk,0,sizeof(rk));
		memset(c,0,sizeof(c));
		memset(k,0,sizeof(k));
		memset(kt.tr.mx,0,sizeof(kt.tr.mx));
		cnt=0;
	}
	inline void In(){
		Clear();
		n=rnt();
		_for(i,1,n-1){
			ll u=rnt(),v=rnt(),w=rnt();
			e[i]=(Edge){u,v,w};
			tu[u].push_back(make_pair(v,w));
			tu[v].push_back(make_pair(u,w));
		}
		kt.Build();
		while(1){
			char op=rch();
			if(op=='C'){
				ll a=rnt(),b=rnt();
				kt.Update(e[a].u,e[a].v,b);
			}
			else if(op=='Q'){
				ll a=rnt(),b=rnt();
				printf("%lld\n",kt.Query(a,b));
			}
			else return;
		}
		return;
	}
}

using namespace std;
const ll N=2e5+10,inf=1ll<<40;
ll n,q,c[N];
vector<ll>tu[N];
ll fa[N],dep[N],sz[N],son[N];
ll cnt,top[N],dfn[N],rk[N];
class KillTree{
public:
	class SegmentTree{
	public:
		class TREE{public:ll val,sz,tag;}tr[N<<2];
		#define va(p) tr[p].val
		#define sz(p) tr[p].sz
		#define ta(p) tr[p].tag
		#define ls(p) (p<<1)
		#define rs(p) (p<<1|1)
		#define l_s(p) ls(p),l,mid
		#define r_s(p) rs(p),mid+1,r
		inline void Tag(ll p,ll tg){va(p)+=tg*sz(p),ta(p)+=tg;}
		inline void PushUp(ll p){va(p)=va(ls(p))+va(rs(p));}
		inline void PushDown(ll p){
			if(!ta(p))return;
			Tag(ls(p),ta(p));
			Tag(rs(p),ta(p));
			ta(p)=0;
			return;
		}
		void Build(ll p,ll l,ll r){
			sz(p)=r-l+1,ta(p)=0;
			if(l==r)va(p)=c[rk[l]];
			else{
				bdmd;
				Build(l_s(p));
				Build(r_s(p));
				PushUp(p);
			}
			return;
		}
		void Update(ll p,ll l,ll r,ll le,ll ri,ll val){
			if(ri<l||r<le)return;
			PushDown(p);
			if(le<=l&&r<=ri)Tag(p,val);
			else{
				bdmd;
				Update(l_s(p),le,ri,val);
				Update(r_s(p),le,ri,val);
				PushUp(p);
			}
			return;
		}
		ll Query(ll p,ll l,ll r,ll le,ll ri){
			if(ri<l||r<le)return 0;
			PushDown(p);
			if(le<=l&&r<=ri)return va(p);
			else{
				bdmd;
				ll ans1=Query(l_s(p),le,ri);
				ll ans2=Query(r_s(p),le,ri);
				return ans1+ans2;
			}
		}
	}tr;
	void Dfs1(ll u){
		sz[u]=1,son[u]=-1;
		far(v,tu[u]){
			if(v==fa[u])continue;
			fa[v]=u,dep[v]=dep[u]+1;
			Dfs1(v);
			sz[u]+=sz[v];
			if(son[u]==-1||sz[son[u]]<sz[v])son[u]=v;
		}
		return;
	}
	void Dfs2(ll u,ll t){
		top[u]=t;
		dfn[u]=++cnt;
		rk[cnt]=u;
		if(son[u]==-1)return;
		Dfs2(son[u],t);
		far(v,tu[u])if(v!=fa[u]&&v!=son[u])Dfs2(v,v);
		return; 
	}
	inline void Build(){Dfs1(1),Dfs2(1,1),tr.Build(1,1,n);}
	inline void UpdateP(ll x,ll val){tr.Update(1,1,n,dfn[x],dfn[x],val);}
	inline void UpdateR(ll x,ll val){tr.Update(1,1,n,dfn[x],dfn[x]+sz[x]-1,val);}
	inline ll Query(ll x){
		ll num=0,tx=top[x];
		while(tx>=1){
			num+=tr.Query(1,1,n,dfn[tx],dfn[x]);
			x=fa[tx],tx=top[x];
		}
		return num;
	}
}kt;
namespace SOLVE{
	inline ll rnt(){
		ll x=0,w=1;char c=getchar();
		while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
		while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
		return x*w;
	}
	inline char rch(){
		char c=getchar();
		while(c<'A'||c>'Z')c=getchar();
		return c;
	}
	inline void In(){
		n=rnt(),q=rnt();
		_for(i,1,n)c[i]=rnt();
		_for(i,1,n-1){
			ll u=rnt(),v=rnt();
			tu[u].push_back(v);
			tu[v].push_back(u);
		}
		kt.Build();
		_for(i,1,q){
			ll op=rnt(),a=rnt(),b=0;
			if(op==1)b=rnt(),kt.UpdateP(a,b);
			else if(op==2)b=rnt(),kt.UpdateR(a,b);
			else printf("%lld\n",kt.Query(a));
		}
		return;
	}
}

const ll N=1e5+10,inf=1ll<<40;
ll n,m,q,c[N],k[N];
vector<pair<ll,ll> >tu[N];
ll fa[N],dep[N],sz[N],son[N];
ll cnt,top[N],dfn[N],rk[N];
class BCJ{
public:
	ll f[N];
	inline void Pre(){_for(i,1,n)f[i]=i;}
	ll Find(ll x){return (f[x]==x)?x:(f[x]=Find(f[x]));}
	inline void Merge(ll x,ll y){f[y]=x;}
}bcj;
namespace Kru{
	class Edge{
	public:
		ll u,v,w;
		inline bool operator<(const Edge &d)const{return w>d.w;}
	}e[N];
	inline void Add(ll i,ll u,ll v,ll w){e[i].u=u,e[i].v=v,e[i].w=w;}
	inline void Solve(){
		sort(e+1,e+m+1);
		ll k=0;
		bcj.Pre();
		_for(i,1,m){
			ll fu=bcj.Find(e[i].u),fv=bcj.Find(e[i].v);
			if(fu!=fv){
				tu[e[i].u].push_back(make_pair(e[i].v,e[i].w));
				tu[e[i].v].push_back(make_pair(e[i].u,e[i].w));
				bcj.Merge(fu,fv);
				++k;
			}
			if(k==n-1)break;
		}
		return;
	}
}
class KillTree{
public:
	class SegmentTree{
	public:
		class TREE{public:ll mn;}tr[N<<2];
		#define mn(p) tr[p].mn
		#define ls(p) (p<<1)
		#define rs(p) (p<<1|1)
		#define l_s(p) (p<<1),l,mid
		#define r_s(p) (p<<1|1),mid+1,r
		void Build(ll p,ll l,ll r){
			if(l==r)mn(p)=c[rk[l]]?c[rk[l]]:inf;
			else{
				bdmd;
				Build(l_s(p)),Build(r_s(p));
				mn(p)=min(mn(ls(p)),mn(rs(p)));
			}
			return;
		}
		ll Query(ll p,ll l,ll r,ll le,ll ri){
			if(ri<l||r<le)return inf;
			if(le<=l&&r<=ri)return mn(p);
			else{
				bdmd;
				return min(Query(l_s(p),le,ri),Query(r_s(p),le,ri));
			}
		}
	}tr;
	void Dfs1(ll u){
		sz[u]=1,son[u]=-1;
		far(pr,tu[u]){
			ll v=pr.first,w=pr.second;
			if(v==fa[u])continue;
			c[v]=w,fa[v]=u,dep[v]=dep[u]+1;
			Dfs1(v);
			sz[u]+=sz[v];
			if(son[u]==-1||sz[son[u]]<sz[v])son[u]=v;
		}
		return;
	}
	void Dfs2(ll u,ll t){
		top[u]=t;
		dfn[u]=++cnt;
		rk[cnt]=u;
		if(son[u]==-1)return;
		Dfs2(son[u],t);
		far(pr,tu[u]){
			ll v=pr.first;
			if(v!=fa[u]&&v!=son[u])Dfs2(v,v);
		}
		return;
	}
	inline void Build(){Dfs1(1),Dfs2(1,1),tr.Build(1,1,n);}
	inline ll Query(ll x,ll y){
		if(bcj.Find(x)!=bcj.Find(y))return -1;
		ll num=inf,tx=top[x],ty=top[y];
		while(tx!=ty){
			if(dep[tx]<dep[ty])swap(x,y),swap(tx,ty);
			num=min(num,tr.Query(1,1,n,dfn[tx],dfn[x]));
			x=fa[tx],tx=top[x];
		}
		if(x!=y)num=min(num,tr.Query(1,1,n,min(dfn[x],dfn[y])+1,max(dfn[x],dfn[y])));
		return num;
	}
}kt;
namespace SOLVE{
	inline ll rnt(){
		ll x=0,w=1;char c=getchar();
		while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
		while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
		return x*w;
	}
	inline char rch(){
		char c=getchar();
		while(c<'A'||c>'Z')c=getchar();
		return c;
	}
	inline void In(){
		n=rnt(),m=rnt();
		_for(i,1,m){
			ll u=rnt(),v=rnt(),w=rnt();
			Kru::Add(i,u,v,w);
		}
		Kru::Solve();
		kt.Build();
		q=rnt();
		_for(i,1,q){
			ll x=rnt(),y=rnt();
			printf("%lld\n",kt.Query(x,y));
		}
		return;
	}
}

const ll N=3e6+10,inf=1ll<<40;
ll n,m,q,c[N],ans=inf,lgst,lx,ly;
vector<pair<ll,ll> >tu[N];
ll fa[N],dep[N],sz[N],son[N];
ll cnt,top[N],dfn[N],rk[N];
class KillTree{
public:
	class TreeArray{
	public:
		ll b[N];
		inline void Update(ll x,ll y){while(x&&x<=n)b[x]+=y,x+=(x&-x);}
		inline ll Query(ll x){ll sum=0;while(x)sum+=b[x],x-=(x&-x);return sum;}
		inline void Build(){_for(i,1,n)Update(i,c[rk[i]]);}
	}tra;
	class SegmentTree{
	public:
		class Tree{public:ll mx,tag,sz;}tr[N<<2];
		#define sz(p) tr[p].sz
		#define mx(p) tr[p].mx
		#define ta(p) tr[p].tag
		#define ls(p) (p<<1)
		#define rs(p) (p<<1|1)
		#define l_s(p) (p<<1),l,mid
		#define r_s(p) (p<<1|1),mid+1,r
		inline void Tag(ll p,ll tg){if(tg>ta(p))ta(p)=tg,mx(p)=max(mx(p),tg);}
		inline void PushUp(ll p){mx(p)=max(mx(ls(p)),mx(rs(p)));}
		inline void PushDown(ll p){if(ta(p))Tag(ls(p),ta(p)),Tag(rs(p),ta(p)),ta(p)=0;}
		void Build(ll p,ll l,ll r){
			ta(p)=0,sz(p)=r-l+1;
			if(l==r)mx(p)=0;
			else{
				bdmd;
				Build(l_s(p)),Build(r_s(p));
				PushUp(p);
			}
			return;
		}
		void Update(ll p,ll l,ll r,ll le,ll ri,ll val){
			if(ri<l||r<le)return;
			PushDown(p);
			if(le<=l&&r<=ri)Tag(p,val);
			else{
				bdmd;
				Update(l_s(p),le,ri,val);
				Update(r_s(p),le,ri,val);
				PushUp(p);
			}
		}
		ll Query(ll p,ll l,ll r,ll x){
			if(x<l||r<x)return 0;
			PushDown(p);
			if(l==r)return mx(p);
			else{
				bdmd;
				return max(Query(l_s(p),x),Query(r_s(p),x));
			}
		}
	}set;
	void Dfs1(ll u){
		sz[u]=1,son[u]=-1;
		far(pr,tu[u]){
			ll v=pr.first,w=pr.second;
			if(v==fa[u])continue;
			fa[v]=u,dep[v]=dep[u]+1,c[v]=w;
			Dfs1(v);
			sz[u]+=sz[v];
			if(son[u]==-1||sz[son[u]]<sz[v])son[u]=v;
		}
		return;
	}
	void Dfs2(ll u,ll t){
		top[u]=t;
		dfn[u]=++cnt;
		rk[cnt]=u;
		if(son[u]==-1)return;
		Dfs2(son[u],t);
		far(pr,tu[u]){
			ll v=pr.first;
			if(v!=fa[u]&&v!=son[u])Dfs2(v,v);
		}
		return;
	}
	inline void Build(){Dfs1(1),Dfs2(1,1),tra.Build(),set.Build(1,1,n);}
	inline ll Query(ll x,ll y){
		ll num=0,tx=top[x],ty=top[y];
		while(tx!=ty){
			if(dep[tx]<dep[ty])swap(x,y),swap(tx,ty);
			num+=tra.Query(dfn[x])-tra.Query(dfn[tx]-1);
			x=fa[tx],tx=top[x];
		}
		num+=tra.Query(max(dfn[x],dfn[y]))-tra.Query(min(dfn[x],dfn[y]));
		return num;
	}
	inline void Add(ll x,ll y){
		ll tx=top[x],ty=top[y],num=Query(x,y);
		if(num>lgst)lgst=num,lx=x,ly=y;
		vector<pair<ll,ll> >e;
		while(tx!=ty){
			if(dep[tx]<dep[ty])swap(x,y),swap(tx,ty);
			e.push_back(make_pair(dfn[tx],dfn[x]));
			x=fa[tx],tx=top[x];
		}
		if(dep[x]<dep[y])swap(x,y);
		e.push_back(make_pair(dfn[y]+1,dfn[x]));
		sort(e.begin(),e.end());
		if(!e.empty()){
			ll sz=e.size()-1;
			if(e[0].first!=1)set.Update(1,1,n,1,e[0].first-1,num);
			if(e[sz].second!=n)set.Update(1,1,n,e[sz].second+1,n,num);
			_for(i,1,sz){
				if(e[i-1].second+1==e[i].first)continue;
				set.Update(1,1,n,e[i-1].second+1,e[i].first-1,num);
			}
		}
		return;
	}
	inline ll Solve(){
		while(lx!=ly){
			if(dep[lx]<dep[ly])swap(lx,ly);
			ans=min(ans,max(lgst-c[lx],set.Query(1,1,n,dfn[lx])));
			lx=fa[lx];
		}
		return ans;
	}
}kt;
namespace SOLVE{
	inline ll rnt(){
		ll x=0,w=1;char c=getchar();
		while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
		while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
		return x*w;
	}
	inline char rch(){
		char c=getchar();
		while(c<'A'||c>'Z')c=getchar();
		return c;
	}
	inline void In(){
		n=rnt(),m=rnt();
		_for(i,1,n-1){
			ll u=rnt(),v=rnt(),w=rnt();
			tu[u].push_back(make_pair(v,w));
			tu[v].push_back(make_pair(u,w));
		}
		kt.Build();
		_for(i,1,m){
			ll x=rnt(),y=rnt();
			if(x!=y)kt.Add(x,y);
		}
		printf("%lld\n",kt.Solve()%inf);
		return;
	}
}

const ll N=2e5+10,inf=1ll<<40;
ll n,m,root,val[N],ans;
vector<ll>tu[N];
ll fa[N],dep[N],sz[N],son[N];
ll cnt,top[N],dfn[N],rk[N];
class KillTree{
public:
	class SegmentTree{
	public:
		class{public:ll va,ta;}tr[N<<2];
		#define va(p) tr[p].va
		#define ta(p) tr[p].ta
		#define ls(p) (p<<1)
		#define rs(p) (p<<1|1)
		#define l_s(p) (p<<1),l,mid
		#define r_s(p) (p<<1|1),mid+1,r
		inline void Tag(ll p,ll tg){va(p)=ta(p)=tg;return;}
		inline void PushUp(ll p){va(p)=min(va(ls(p)),va(rs(p)));}
		inline void PushDown(ll p){
			if(ta(p)==-1)return;
			Tag(ls(p),ta(p));
			Tag(rs(p),ta(p));
			ta(p)=-1;
			return;
		}
		void Build(ll p,ll l,ll r){
			ta(p)=-1;
			if(l==r)va(p)=val[rk[l]];
			else{
				bdmd;
				Build(l_s(p)),Build(r_s(p));
				PushUp(p);
			}
			return;
		}
		void Update(ll p,ll l,ll r,ll le,ll ri,ll val){
			if(ri<l||r<le)return;
			PushDown(p);
			if(le<=l&&r<=ri)Tag(p,val);
			else{
				bdmd;
				Update(l_s(p),le,ri,val);
				Update(r_s(p),le,ri,val);
				PushUp(p);
			}
			return;
		}
		ll Query(ll p,ll l,ll r,ll le,ll ri){
			if(ri<l||r<le)return inf;
			PushDown(p);
			if(le<=l&&r<=ri)return va(p);
			else{
				bdmd;
				return min(Query(l_s(p),le,ri),Query(r_s(p),le,ri));
			}
		}
	}tr;
	void Dfs1(ll u){
		sz[u]=1,son[u]=-1;
		far(v,tu[u]){
			if(v==fa[u])continue;
			fa[v]=u,dep[v]=dep[u]+1;
			Dfs1(v);
			sz[u]+=sz[v];
			if(son[u]==-1||sz[son[u]]<sz[v])son[u]=v;
		}
		return;
	}
	void Dfs2(ll u,ll t){
		top[u]=t;
		dfn[u]=++cnt;
		rk[cnt]=u;
		if(son[u]==-1)return;
		Dfs2(son[u],t);
		far(v,tu[u])if(v!=fa[u]&&v!=son[u])Dfs2(v,v);
		return;
	}
	inline void Build(){Dfs1(1),Dfs2(1,1),tr.Build(1,1,n);}
	inline void Update(ll x,ll y,ll z){
		ll tx=top[x],ty=top[y];
		while(tx!=ty){
			if(dep[tx]<dep[ty])swap(x,y),swap(tx,ty);
			tr.Update(1,1,n,dfn[tx],dfn[x],z);
			x=fa[tx],tx=top[x];
		}
		if(dep[x]<dep[y])swap(x,y);
		tr.Update(1,1,n,dfn[y],dfn[x],z);
	}
	inline ll Query(ll x,ll y){
		ll q=x,tx=top[x],ty=top[y],s=x;
		while(tx!=ty){
			if(dep[tx]<dep[ty])s=y,y=fa[ty],ty=top[y];
			else x=fa[tx],tx=top[x];
		}
		if(x!=y)s=son[x];
		if(dep[x]>dep[y])swap(x,y);
		if(q==root)return tr.Query(1,1,n,1,n);
		else if(x!=q)return tr.Query(1,1,n,dfn[q],dfn[q]+sz[q]-1);
		else return min(tr.Query(1,1,n,1,dfn[s]-1),tr.Query(1,1,n,dfn[s]+sz[s],n));
	}
}kt;
namespace SOLVE{
	inline ll rnt(){
		ll x=0,w=1;char c=getchar();
		while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
		while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
		return x*w;
	}
	inline void In(){
		n=rnt(),m=rnt(),root=1;
		_for(i,1,n-1){
			ll u=rnt(),v=rnt();
			tu[u].push_back(v);
			tu[v].push_back(u);
		}
		_for(i,1,n)val[i]=rnt();
		root=rnt();
		kt.Build();
		_for(i,1,m){
			ll op=rnt();
			if(op==1)root=rnt();
			else if(op==2){
				ll x=rnt(),y=rnt(),z=rnt();
				kt.Update(x,y,z);
			}
			else{
				ll x=rnt();
				printf("%lld\n",kt.Query(x,root));
			}
		}
		return;
	}
}