/* 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。
有没有大佬帮忙看一下为什么。