树链剖分+线段树lazy-tag
在树链上操作时千万不要写错。。
/* 树链剖分+线段树区间变负 */ #include<iostream> #include<cstring> #include<cstdio> using namespace std; #define maxn 10005 struct Edge{ int to,next; }edge[maxn<<1]; int head[maxn],tot,e[maxn][3]; int fa[maxn],son[maxn],num[maxn],deep[maxn]; int top[maxn],fp[maxn],p[maxn],pos; inline void addedge(int u,int v){ edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++; } void dfs1(int u,int pre,int dep){ fa[u]=pre;num[u]=1;deep[u]=dep; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==pre) continue; dfs1(v,u,dep+1); num[u]+=num[v]; if(son[u]==-1 || num[son[u]]<num[v]) son[u]=v; } } void getpos(int u,int sp){ top[u]=sp;p[u]=pos++;fp[p[u]]=u; if(son[u]==-1) return; getpos(son[u],sp); for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v!=fa[u] && v!=son[u]) getpos(v,v); } } #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 int Max[maxn<<2],Min[maxn<<2],rev[maxn<<2];//遇到区间取反的通常维护一下区间两个极值 void build(int l,int r,int rt){ Max[rt]=Min[rt]=rev[rt]=0; if(l==r) return; int m=l+r>>1; build(lson);build(rson); } inline void pushup(int rt){ Max[rt]=max(Max[rt<<1],Max[rt<<1|1]); Min[rt]=min(Min[rt<<1],Min[rt<<1|1]); } inline void pushdown(int rt){ if(rev[rt]){ rev[rt<<1]^=1,rev[rt<<1|1]^=1; swap(Min[rt<<1],Max[rt<<1]); Min[rt<<1]*=-1,Max[rt<<1]*=-1; swap(Min[rt<<1|1],Max[rt<<1|1]); Min[rt<<1|1]*=-1,Max[rt<<1|1]*=-1; rev[rt]=0; } } void update(int pos,int val,int l,int r,int rt){ if(l==r){Max[rt]=Min[rt]=val;rev[rt]=0;return;} int m=l+r>>1; pushdown(rt); if(pos<=m) update(pos,val,lson); else update(pos,val,rson); pushup(rt); } void seg_negate(int L,int R,int l,int r,int rt){ if(L<=l && R>=r){ swap(Min[rt],Max[rt]); Min[rt]*=-1,Max[rt]*=-1; rev[rt]^=1; return; } pushdown(rt); int m=l+r>>1; if(L<=m) seg_negate(L,R,lson); if(R>m) seg_negate(L,R,rson); pushup(rt); } int query(int L,int R,int l,int r,int rt){ if(L<=l && R>=r)return Max[rt]; pushdown(rt); int m=l+r>>1,res=-100000000; if(L<=m) res=max(res,query(L,R,lson)); if(R>m) res=max(res,query(L,R,rson)); pushup(rt); return res; } int find(int u,int v)//查询u->v边的最大值 { int f1 = top[u], f2 = top[v]; int tmp = -100000000; while(f1 != f2) { if(deep[f1] < deep[f2]) { swap(f1,f2); swap(u,v); } tmp = max(tmp,query(p[f1],p[u],0,pos,1)); u = fa[f1]; f1 = top[u]; } if(u == v)return tmp; if(deep[u] > deep[v]) swap(u,v); return max(tmp,query(p[son[u]],p[v],0,pos,1)); } void Negate(int u,int v)//把u-v路径上的边的值都设置为val { int f1 = top[u], f2 = top[v]; while(f1 != f2) { if(deep[f1] < deep[f2]) { swap(f1,f2); swap(u,v); } seg_negate(p[f1],p[u],0,pos,1); u = fa[f1]; f1 = top[u]; } if(u == v)return; if(deep[u] > deep[v]) swap(u,v); return seg_negate(p[son[u]],p[v],0,pos,1); } void init(){ tot=pos=0; memset(head,-1,sizeof head); memset(son,-1,sizeof son); } int main(){ int T,n,a,b,c; char op[10]; cin >> T; while(T--){ init(); scanf("%d",&n); for(int i=1;i<=n-1;i++){ scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]); addedge(e[i][0],e[i][1]);addedge(e[i][1],e[i][0]); } dfs1(1,0,0);getpos(1,1);build(0,pos,1); for(int i=1;i<=n-1;i++){ if(deep[e[i][0]]>deep[e[i][1]]) swap(e[i][0],e[i][1]); update(p[e[i][1]],e[i][2],0,pos,1); } while(scanf("%s",op)){ if(op[0]=='D') break; scanf("%d%d",&a,&b); if(op[0]=='C')update(p[e[a][1]],b,0,pos,1); else if(op[0]=='N') Negate(a,b); else printf("%d ",find(a,b)); } } }