[国家集训队]旅游

link

很简单一道题，评紫实在是有点暴殄天物。边权下放到点权然后查询时注意不要查找lca的值即可。本来以为在区间取反的基础上还有个区间加所以双lazy还有点麻烦时，突然发现它似乎只有单点修改。

唯一不好的事就是我把树剖的板子打错了。应该判的是top的深度大小，然后我tmd竟然把这茬给忘了。于是调了两个小时，最后在翻原来树剖的代码时偶然发现。操。

#include
//#define zczc
const int N=200010;
const int inf=1e9;
inline void read(int &wh){
    wh=0;int f=1;char w=getchar();
    while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
    while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}
    wh*=f;return;
}
inline int op(){
	char w[10];scanf("%s",w);
	switch(w[0]){
		case 'C':return 0;break;
		case 'N':return 1;break;
		case 'S':return 2;break;
		case 'M':return w[1]=='A'?3:4;break;
	}
}
inline void swap(int &s1,int &s2){
	int s3=s1;s1=s2;s2=s3;return;
}
inline int max(int s1,int s2){
	return s1size[son[wh]])son[wh]=th;
	}
}

int cnt,id[N],top[N],fir[N];
void dfs2(int wh,int ntop){
	id[wh]=++cnt;top[wh]=ntop;
	if(son[wh])dfs2(son[wh],ntop);
	for(int i=head[wh],th;i;i=e[i].next){
		if((th=e[i].t)==f[wh]||th==son[wh])continue;
		dfs2(th,th);
	}
}

#define lc (wh<<1)
#define rc (wh<<1|1)
#define mid (t[wh].l+t[wh].r>>1)
#define num (t[wh].r-t[wh].l+1)
struct node{
	int l,r,sum,maxn,minn;
	bool lazy;
}t[N<<2];
inline void pushup(int wh){
	t[wh].sum=t[lc].sum+t[rc].sum;
	t[wh].maxn=max(t[lc].maxn,t[rc].maxn);
	t[wh].minn=min(t[lc].minn,t[rc].minn);
}
inline void pushnow(int wh){
	swap(t[wh].maxn,t[wh].minn);
	t[wh].lazy^=1;t[wh].maxn*=-1;
	t[wh].minn*=-1;t[wh].sum*=-1;
}
inline void pushdown(int wh){
	if(!t[wh].lazy)return;t[wh].lazy=false;
	pushnow(lc);pushnow(rc);
}
inline void build(int wh,int l,int r){
	t[wh].l=l,t[wh].r=r;
	if(l==r){t[wh].maxn=t[wh].minn=t[wh].sum=fir[l];return;}
	build(lc,l,mid);build(rc,mid+1,r);pushup(wh);
}
inline void update(int wh,int pl,int val){
	if(t[wh].l==t[wh].r){t[wh].sum=t[wh].maxn=t[wh].minn=val;return;}
	pushdown(wh);update(pl<=mid?lc:rc,pl,val);pushup(wh);
}
inline void change(int wh,int wl,int wr){
	if(wl<=t[wh].l&&t[wh].r<=wr){pushnow(wh);return;}
	pushdown(wh);if(wl<=mid)change(lc,wl,wr);if(wr>mid)change(rc,wl,wr);pushup(wh);
}
int ansum,anmin,anmax;
inline void work(int wh,int wl,int wr){
	if(wl<=t[wh].l&&t[wh].r<=wr){
		ansum+=t[wh].sum;anmin=min(anmin,t[wh].minn);anmax=max(anmax,t[wh].maxn);return;
	}
	pushdown(wh);if(wl<=mid)work(lc,wl,wr);if(wr>mid)work(rc,wl,wr);pushup(wh);
}
#undef lc
#undef rc
#undef mid
#undef num

int ev[N];

signed main(){
	
	#ifdef zczc
	freopen("in.txt","r",stdin);
	#endif
	
	read(m);int s1,s2,s3;
	for(int i=1;i>1;
		ev[now]=id[d[e[i].t]d[s2])swap(s1,s2);
			if(s1^s2)change(1,id[s1]+1,id[s2]);
		}
		if(o>1){
			ansum=0;anmax=-inf;anmin=inf;
			while(top[s1]^top[s2]){
				if(d[top[s1]]d[s2])swap(s1,s2);
			if(s1^s2)work(1,id[s1]+1,id[s2]);
			if(o==2)printf("%d\n",ansum);
			if(o==3)printf("%d\n",anmax);
			if(o==4)printf("%d\n",anmin);
		}
	}
	
	return 0;
}