一棵树上有n个节点,编号分别为1到n,每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作: I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 III. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意:从点u到点v的路径上的节点包括u和v本身
我觉得作为我刷的第一道树链剖分作为模板还是要补一下题解的。
线段树上的操作没什么好说的,主要是query_max和query_sum
比如说我们要求x,y中间路径上的和
我们比较top[x],top[y]即f1,f2的深度
选比较大的那个
取出tid[f1]与tid[x]上的信息
然后x=fa[f1]向上找另一条重链
做到f1=f2为止
最后还有[x,y]的
恩大概就是这样了
那么
var a,head,vet,next,fa,dep,size,flag,tid,son,top,pre, tree_max,tree_sum,isok:array[1..400010]of longint; ch:string; x,y,n,i,m,j,len,tot,time:longint; procedure swap(var x,y:longint); var t:longint; begin t:=x; x:=y; y:=t; end; procedure add(a,b:longint); begin inc(tot); next[tot]:=head[a]; vet[tot]:=b; head[a]:=tot; end; procedure dfs1(u,father,depth:longint); var e,v,maxsize:longint; begin fa[u]:=father; dep[u]:=depth; size[u]:=1; maxsize:=0; son[u]:=0; flag[u]:=1; e:=head[u]; while e<>0 do begin v:=vet[e]; if flag[v]=0 then begin isok[e]:=1; dfs1(v,u,depth+1); size[u]:=size[u]+size[v]; if size[v]>maxsize then begin maxsize:=size[v]; son[u]:=v; end; end; e:=next[e]; end; end; procedure dfs2(u,ance:longint); var e,v:longint; begin inc(time); tid[u]:=time; pre[time]:=u; top[u]:=ance; flag[u]:=1; if son[u]<>0 then dfs2(son[u],ance); e:=head[u]; while e<>0 do begin v:=vet[e]; if (isok[e]=1)and(flag[v]=0) then dfs2(v,v); e:=next[e]; end; end; function max(x,y:longint):longint; begin if x>y then exit(x); exit(y); end; procedure build(l,r,p:longint); var mid:longint; begin if l=r then begin tree_sum[p]:=a[pre[l]]; tree_max[p]:=a[pre[l]]; exit; end; mid:=(l+r)>>1; build(l,mid,p<<1); build(mid+1,r,p<<1+1); tree_sum[p]:=tree_sum[p<<1]+tree_sum[p<<1+1]; tree_max[p]:=max(tree_max[p<<1],tree_max[p<<1+1]); end; procedure update(l,r,x,v,p:longint); var mid:longint; begin if l=r then begin tree_sum[p]:=v; tree_max[p]:=v; exit; end; mid:=(l+r)>>1; if x<=mid then update(l,mid,x,v,p<<1); if x>mid then update(mid+1,r,x,v,p<<1+1); tree_sum[p]:=tree_sum[p<<1]+tree_sum[p<<1+1]; tree_max[p]:=max(tree_max[p<<1],tree_max[p<<1+1]); end; function search_max(l,r,x,y,p:longint):longint; var mid:longint; begin if (l=x)and(r=y) then exit(tree_max[p]); mid:=(l+r)>>1; if y<=mid then exit(search_max(l,mid,x,y,p<<1)) else if x>mid then exit(search_max(mid+1,r,x,y,p<<1+1)) else exit(max(search_max(l,mid,x,mid,p<<1), search_max(mid+1,r,mid+1,y,p<<1+1))); end; function search_sum(l,r,x,y,p:longint):longint; var mid:longint; begin if (l=x)and(r=y) then exit(tree_sum[p]); mid:=(l+r)>>1; if y<=mid then exit(search_sum(l,mid,x,y,p<<1)) else if x>mid then exit(search_sum(mid+1,r,x,y,p<<1+1)) else exit(search_sum(l,mid,x,mid,p<<1)+ search_sum(mid+1,r,mid+1,y,p<<1+1)); end; function query_max(x,y:longint):longint; var f1,f2,t,ans:longint; begin f1:=top[x]; f2:=top[y]; ans:=-maxlongint div 3; while f1<>f2 do begin if dep[f1]<dep[f2] then begin t:=f1; f1:=f2; f2:=t; t:=x; x:=y; y:=t; end; ans:=max(ans,search_max(1,n,tid[f1],tid[x],1)); x:=fa[f1]; f1:=top[x]; end; if dep[x]>dep[y] then ans:=max(ans,search_max(1,n,tid[y],tid[x],1)) else ans:=max(ans,search_max(1,n,tid[x],tid[y],1)); exit(ans); end; function query_sum(x,y:longint):longint; var f1,f2,ans,t:longint; begin f1:=top[x]; f2:=top[y]; ans:=0; while f1<>f2 do begin if dep[f1]<dep[f2] then begin t:=f1; f1:=f2; f2:=t; t:=x; x:=y; y:=t; end; ans:=ans+search_sum(1,n,tid[f1],tid[x],1); x:=fa[f1]; f1:=top[x]; end; if dep[x]>dep[y] then ans:=ans+search_sum(1,n,tid[y],tid[x],1) else ans:=ans+search_sum(1,n,tid[x],tid[y],1); //exit(ans); end; begin readln(n); for i:=1 to n-1 do begin readln(x,y); add(x,y); add(y,x); end; for i:=1 to n do read(a[i]); readln; dfs1(1,-1,1); fillchar(flag,sizeof(flag),0); dfs2(1,1); fillchar(tree_max,sizeof(tree_max),$8f); build(1,n,1); readln(m); for i:=1 to m do begin readln(ch); len:=length(ch); x:=0; y:=0; if ch[1]='C' then begin delete(ch,1,7); val(copy(ch,1,pos(' ',ch)-1),x); val(copy(ch,pos(' ',ch)+1,length(ch)-pos(' ',ch)),y); update(1,n,tid[x],y,1); end else if ch[2]='M' then begin delete(ch,1,5); val(copy(ch,1,pos(' ',ch)-1),x); val(copy(ch,pos(' ',ch)+1,length(ch)-pos(' ',ch)),y); writeln(query_max(x,y)); end else begin delete(ch,1,5); val(copy(ch,1,pos(' ',ch)-1),x); val(copy(ch,pos(' ',ch)+1,length(ch)-pos(' ',ch)),y); writeln(query_sum(x,y)); end; end; end.