Jzoj3898 树的连通性

题意：给一棵树，每次删边或者询问连通性，强制在线

其实这题做法很多嘛，简单说一下

一眼看过去肯定是LCT啦，于是马上开始打

打到一半发现似乎不用LCT？好像树剖也可以嘛

结果发现树剖也不用，直接一个dfs序就可以了嘛

用线段树维护每个点能到达的最远的祖先，删边的时候将整个区间覆盖即可

注意，对于在子树中已经断开的节点不要再覆盖，可以记录每个节点深度

#pragma GCC opitmize("O3")
#pragma G++ opitmize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 200010
using namespace std;
struct Edge{ int v,nt; } G[N<<1];
int h[N],l[N],r[N],s[N<<2],v[N],n,m,cnt=0,clk=0,d[N];
inline void adj(int x,int y){ G[++cnt]=(Edge){y,h[x]}; h[x]=cnt; }
void dfs(int x,int p){
	l[x]=++clk; d[x]=d[p]+1;
	for(int v,i=h[x];i;i=G[i].nt)
		if((v=G[i].v)!=p) dfs(v,x);
	r[x]=clk;
}
inline void pd(int x){ //防止重复覆盖
	if(s[x]){
		int &ls=s[x<<1],&rs=s[x<<1|1];
		if(d[ls]<d[s[x]]) ls=s[x];
		if(d[rs]<d[s[x]]) rs=s[x];
		s[x]=0; 
	}
}
void update(int l,int r,int x,int L,int R,int k){
	if(L<=l && r<=R){ 
		if(!s[x]||d[s[x]]<d[k]) s[x]=k; return; 
	}
	pd(x); int m=l+r>>1;
	if(L<=m) update(l,m,x<<1,L,R,k);
	if(m<R) update(m+1,r,x<<1|1,L,R,k);
}
int query(int l,int r,int x,int k){
	if(l==r) return s[x];
	pd(x); int m=l+r>>1;
	if(k<=m) return query(l,m,x<<1,k);
	else return query(m+1,r,x<<1|1,k);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",v+i);
	for(int x,y,i=1;i<n;++i){
		scanf("%d%d",&x,&y);
		adj(x,y); adj(y,x);
	}
	dfs(1,0); int lst=0; s[1]=1;
	for(int o,a,b;m--;){
		scanf("%d%d%d",&o,&a,&b);
		a^=lst; b^=lst;
		if(o==1){
			if(l[b]>l[a]) a=b;
			update(1,n,1,l[a],r[a],a);
		} else if(o==2){
			if(query(1,n,1,l[a])==query(1,n,1,l[b]))
				printf("%d
",lst=v[a]*v[b]);
			else printf("%d
",lst=v[a]+v[b]);
		} else v[a]=b;
	}
}