神秘CE
查看原帖
神秘CE
557385
cjlak1o1楼主2022/11/16 19:37
/* let life be like summer flowers	*/
/* by wind_seeker					*/
/* 2022-11-16 15:36					*/
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1e3,inf=1e9+7;

inline int read(){
	int res=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) res=(res<<3)+(res<<1)+(c^48);
	return res*f;
}

int n,m,val[N];
struct EDGE{
	int to,w,nxt;
	EDGE(){}
	EDGE(int _to,int _w,int _nxt){to=_to,w=_w,nxt=_nxt;}
}e[N<<2];
int head[N],tot=1,ide[N],eto[N<<2];
void add(int u,int v,int w,int i){e[++tot]=(EDGE){v,w,head[u]},head[u]=tot,ide[i]=tot;}

int sz[N],son[N],dep[N],fat[N];
void dfs1(int u,int fa){
	sz[u]=1,dep[u]=dep[fa]+1,fat[u]=fa;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to,w=e[i].w;if(v==fa) continue;
		eto[i]=eto[i^1]=v,val[v]=w,dfs1(v,u),sz[u]+=sz[v];
		if(sz[son[u]]<sz[v]) son[u]=v;
	}
}
int top[N],dfn[N],id[N],cnt=0;
void dfs2(int u,int htp){
	top[u]=htp;dfn[u]=++cnt,id[cnt]=u;
	if(!son[u]) return;
	dfs2(son[u],htp);
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;if(v==fat[u]||v==son[u]) continue;
		dfs2(v,v);
	}
}

#define ls rt<<1
#define rs rt<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
struct TREE{
	int sum=0,Max=-inf,Min=inf,lazy=0;
}t[N<<2];
void push_up(int rt){t[rt].sum=t[ls].sum+t[rs].sum,t[rt].Max=max(t[ls].Max,t[rs].Max),t[rt].Min=min(t[ls].Min,t[rs].Min);}
void change(int rt){swap(t[rt].Max,t[rt].Min),t[rt].Max*=-1,t[rt].Min*=-1,t[rt].sum*=-1,t[rt].lazy^=1;}
void push_down(int rt){
	if(t[rt].lazy)	change(ls),change(rs),t[rt].lazy^=1;
}
void build(int rt,int l,int r){
	if(l==r&&l!=1) return t[rt].sum=t[rt].Max=t[rt].Min=val[id[l]],void();
	else if(l==r) return t[rt].sum=0,t[rt].Max=-inf,t[rt].Min=inf,void();
	int mid=(l+r)>>1;
	build(lson),build(rson),push_up(rt);
	//printf("l:%d r:%d t[%d].sum:%d\n",l,r,rt,t[rt].Min);
}
void update1(int rt,int l,int r,int pos,int x){
	if(l==r) return t[rt].sum=t[rt].Max=t[rt].Min=x,void();
	push_down(rt);
	int mid=(l+r)>>1;
	if(pos<=mid) update1(lson,pos,x);
	else update1(rson,pos,x);
	push_up(rt);
}
void update2(int rt,int l,int r,int ul,int ur){
	if(ul<=l&&r<=ur) return change(rt),void();
	push_down(rt);
	int mid=(l+r)>>1;
	if(ul<=mid) update2(lson,ul,ur);
	if(mid<ur) update2(rson,ul,ur);
	push_up(rt);
}
int query(int rt,int l,int r,int ql,int qr,int op){
	if(ql<=l&&r<=qr){
		if(op==1) return t[rt].sum;
		if(op==2) return t[rt].Max;
		if(op==3) return t[rt].Min;
	}
	push_down(rt);
	int mid=(l+r)>>1,res=0;
	if(op==1) res=0;if(op==2) res=-inf;if(op==3) res=inf;
	if(ql<=mid){
		int lsum=query(lson,ql,qr,op);
		if(op==1) res+=lsum;if(op==2) res=max(res,lsum);if(op==3) res=min(res,lsum);
	}
	if(mid<qr){
		int rsum=query(rson,ql,qr,op);
		if(op==1) res+=rsum;if(op==2) res=max(res,rsum);if(op==3) res=min(res,rsum);
	}
	return res;
}

int Lca(int x,int y,int op){
	int res=0;
	if(op==1) res=0;if(op==2) res=-inf;if(op==3) res=inf;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		if(!op) update2(1,1,n,dfn[top[x]],dfn[x]);
		else{
			int cal=query(1,1,n,dfn[top[x]],dfn[x],op);
			if(op==1) res+=cal;if(op==2) res=max(res,cal);if(op==3) res=min(res,cal);
		}
		x=fat[top[x]];
	}
	if(dfn[x]<dfn[y]) swap(x,y);
	if(!op) update2(1,1,n,dfn[y]+1,dfn[x]);
	else{
		int cal=query(1,1,n,dfn[y]+1,dfn[x],op);
		if(op==1) res+=cal;if(op==2) res=max(res,cal);if(op==3) res=min(res,cal);
	}
	return res;
}

char op[8];
int main(){
	n=read();
	for(int i=1,u,v,w;i<n;i++) u=read()+1,v=read()+1,w=read(),add(u,v,w,i),add(v,u,w,i);
	dfs1(1,0);dfs2(1,1);build(1,1,n);
	m=read();//cout<<ide[1]<<endl;
	for(int i=1,x,y;i<=m;i++){
		cin>>op;x=read()+1;y=read()+1;
		if(op[0]=='C') update1(1,1,n,dfn[eto[ide[x-1]]],y-1);
		else if(op[0]=='N') Lca(x,y,0);
		else if(op[0]=='S') printf("%d\n",Lca(x,y,1));
		else if(op[1]=='A') printf("%d\n",Lca(x,y,2));
		else printf("%d\n",Lca(x,y,3));
	}
	return 0;
}

该代码在本地编译能通过,但在洛谷上会CE。

而且在结构体 TREE 中四个变量去掉任何一个赋值都能通过,但四个都有就会CE。

有没有大佬帮忙看一下为什么。

2022/11/16 19:37
加载中...