树链剖分模板题
//#include<bits/stdc++.h> #include<iostream> #include<cstring> #include<cstdio> using namespace std; #define MAXN 100010 #define maxint (1<<30) struct Edge{ int to,next; }edge[MAXN<<1]; int n,tot=0,last[MAXN]={}; void add_edge(int a,int b){ ++tot; edge[tot].to=b; edge[tot].next=last[a]; last[a]=tot; } int fa[MAXN],dep[MAXN],num[MAXN],son[MAXN]; void dfs(int x,int v,int d){ fa[x]=v; dep[x]=d; num[x]=1; for(int i=last[x];i;i=edge[i].next) if(edge[i].to!=v){ dfs(edge[i].to,x,d+1); num[x]+=num[edge[i].to]; if(!son[x]||num[edge[i].to]>num[son[x]]) son[x]=edge[i].to; } } int pos=0,top[MAXN],tree[MAXN],id[MAXN]; void dfs_(int x,int v){ top[x]=v; tree[x]=pos; id[pos++]=x; if(!son[x]) return; dfs_(son[x],v); for(int i=last[x];i;i=edge[i].next) if(edge[i].to!=son[x]&&edge[i].to!=fa[x]) dfs_(edge[i].to,edge[i].to); } struct Node{ int max,min,tag; }a[MAXN*3]={}; void pushdown(int x,int l,int r){ if(l==r) return; a[x].tag=0; a[x<<1].max=-a[x<<1].max; a[x<<1].min=-a[x<<1].min; swap(a[x<<1].max,a[x<<1].min); a[x<<1].tag^=1; a[(x<<1)|1].max=-a[(x<<1)|1].max; a[(x<<1)|1].min=-a[(x<<1)|1].min; swap(a[(x<<1)|1].max,a[(x<<1)|1].min); a[(x<<1)|1].tag^=1; } void change(int x,int l,int r,int k,int v){ if(l==r&&l==k){ a[x].max=a[x].min=v; a[x].tag=0; return; } int mid=(l+r)>>1; if(a[x].tag) pushdown(x,l,r); if(k<=mid) change(x<<1,l,mid,k,v); else change((x<<1)|1,mid+1,r,k,v); a[x].max=max(a[x<<1].max,a[(x<<1)|1].max); a[x].min=min(a[x<<1].min,a[(x<<1)|1].min); } void ne_update(int x,int l,int r,int ql,int qr){ if(ql>r||qr<l) return; if(ql<=l&&r<=qr){ a[x].tag^=1; a[x].max=-a[x].max; a[x].min=-a[x].min; swap(a[x].max,a[x].min); return; } int mid=(l+r)>>1; if(a[x].tag) pushdown(x,l,r); ne_update(x<<1,l,mid,ql,qr); ne_update((x<<1)|1,mid+1,r,ql,qr); a[x].max=max(a[x<<1].max,a[(x<<1)|1].max); a[x].min=min(a[x<<1].min,a[(x<<1)|1].min); } int query(int x,int l,int r,int ql,int qr){ if(ql>r||qr<l) return -maxint; if(ql<=l&&r<=qr) return a[x].max; int mid=(l+r)>>1; if(a[x].tag) pushdown(x,l,r); return max(query(x<<1,l,mid,ql,qr),query((x<<1)|1,mid+1,r,ql,qr)); } int findmax(int u,int v){ int res=-maxint; while(top[u]!=top[v]){ if(dep[top[u]]>dep[top[v]]) res=max(res,query(1,1,n,tree[top[u]],tree[u])),u=fa[top[u]]; else res=max(res,query(1,1,n,tree[top[v]],tree[v])),v=fa[top[v]]; } if(dep[u]>dep[v]) swap(u,v); res=max(res,query(1,1,n,tree[son[u]],tree[v])); return res; } void Negate(int u,int v){ while(top[u]!=top[v]){ if(dep[top[u]]>dep[top[v]]) ne_update(1,1,n,tree[top[u]],tree[u]),u=fa[top[u]]; else ne_update(1,1,n,tree[top[v]],tree[v]),v=fa[top[v]]; } if(dep[u]>dep[v]) swap(u,v); ne_update(1,1,n,tree[son[u]],tree[v]); } void init(){ tot=pos=0; memset(last,0,sizeof(last)); memset(son,0,sizeof(son)); memset(a,0,sizeof(a)); } int main(){ int t,a[MAXN],b[MAXN],c[MAXN]; for(scanf("%d",&t);t;t--){ scanf("%d",&n); n--; init(); for(int i=1;i<=n;i++){ scanf("%d%d%d",&a[i],&b[i],&c[i]); add_edge(a[i],b[i]); add_edge(b[i],a[i]); } dfs(1,0,0); dfs_(1,1); for(int i=1;i<=n;i++){ if(dep[a[i]]>dep[b[i]]) swap(a[i],b[i]); change(1,1,n,tree[b[i]],c[i]); } char op[10]; while(~scanf("%s",op)){ if(op[0]=='D') break; int u,v; scanf("%d%d",&u,&v); if(op[0]=='Q') printf("%d ",findmax(u,v)); if(op[0]=='C') change(1,1,n,tree[b[u]],v); if(op[0]=='N') Negate(u,v); } } return 0; }