myx12345's Blog

一棵树上有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.

 有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个

这是我A的第二道树链剖分，A第一道在4个月前。

http://blog.sina.com.cn/s/blog_7a1746820100wp67.html

http://www.tuicool.com/articles/mQB36z

这俩教程不错。

因为以X为根中的子树分成了一条条重链，而他们的编号是连续的。

所以我们可以在DFS2时找到以x为根时它的子树在线段树中的最大编号mx[x]。

然后就是裸地区间修改和求和。

这LCA都不用。

记得大数据题要写成t[p].s:=t[p].s*(r-l+1)*v，v:int64（WA*N）

var t:array[1..500000]of record
                             a,s:int64;
                            end;
    head,vet,next,top,tid,mx,fa,size,a:array[0..200000]of longint;
    n,m,i,x,y,tot,time,ch:longint;

procedure add(a,b:longint);
begin
 inc(tot);
 next[tot]:=head[a];
 vet[tot]:=b;
 head[a]:=tot;
end;

function max(x,y:longint):longint;
begin
 if x>y then exit(x);
 exit(y);
end;

function min(x,y:longint):longint;
begin
 if x<y then exit(X);
 exit(y);
end;

procedure dfs1(u:longint);
var e,v:longint;
begin
 size[u]:=1;
 e:=head[u];
 while e<>0 do
 begin
  v:=vet[e];
  if v<>fa[u] then
  begin
   fa[v]:=u;
   dfs1(v);
   size[u]:=size[u]+size[v];
   mx[u]:=max(mx[u],mx[v]);
  end;
  e:=next[e];
 end;
end;

procedure dfs2(u,ance:longint);
var e,v,k:longint;
begin
 inc(time); tid[u]:=time; top[u]:=ance; mx[u]:=time;
 e:=head[u];
 k:=0;
 while e<>0 do
 begin
  v:=vet[e];
  if (v<>fa[u])and(size[v]>size[k]) then k:=v;
  e:=next[e];
 end;
 if k>0 then
 begin
  dfs2(k,ance);
  mx[u]:=max(mx[u],mx[k]);
 end;
 e:=head[u];
 while e<>0 do
 begin
  v:=vet[e];
  if (v<>fa[u])and(v<>k) then
  begin
   dfs2(v,v);
   mx[u]:=max(mx[u],mx[v]);
  end;
  e:=next[e];
 end;
end;

procedure pushdown(l,r,p:longint);
var mid,ls,rs:longint;
begin
 if l=r then exit;
 mid:=(l+r)>>1;
 ls:=p<<1; rs:=ls+1;
 t[ls].a:=t[ls].a+t[p].a;
 t[rs].a:=t[rs].a+t[p].a;
 t[ls].s:=t[ls].s+(mid-l+1)*t[p].a;
 t[rs].s:=t[rs].s+(r-mid)*t[p].a;
 t[p].a:=0;
end;

function query(l,r,x,y,p:longint):int64;
var mid:longint;
begin
 if (l>=x)and(r<=y) then exit(t[p].s);
 pushdown(l,r,p);
 mid:=(l+r)>>1;
 query:=0;
 if x<=mid then query:=query+query(l,mid,x,y,p<<1);
 if y>mid then query:=query+query(mid+1,r,x,y,p<<1+1);
end;

function querys(x:longint):int64;
begin
 querys:=0;
 while top[x]<>1 do
 begin
  querys:=querys+query(1,n,tid[top[x]],tid[x],1);
  x:=fa[top[x]];
 end;
 querys:=querys+query(1,n,1,tid[x],1);
end;

procedure update(l,r,x,y:longint;v:int64;p:longint);
var mid:longint;
begin
 if (l>=x)and(r<=y) then
 begin
  t[p].a:=t[p].a+v;
  t[p].s:=t[p].s+v*(r-l+1);
  exit;
 end;
 pushdown(l,r,p);
 mid:=(l+r)>>1;
 if x<=mid then update(l,mid,x,y,v,p<<1);
 if y>mid then update(mid+1,r,x,y,v,p<<1+1);
 t[p].s:=t[p<<1].s+t[p<<1+1].s;
end;


begin
 assign(input,'1.in'); reset(input);
 assign(output,'1.out'); rewrite(output);
 read(n,m);
 for i:=1 to n do read(a[i]);
 for i:=1 to n-1 do
 begin
  read(x,y);
  add(x,y);
  add(y,x);
 end;
 dfs1(1);
 dfs2(1,1);
 for i:=1 to n do update(1,n,tid[i],tid[i],a[i],1);

 for i:=1 to m do
 begin
  read(ch);
  case ch of
   1:
   begin
    read(x,y);
    update(1,n,tid[x],tid[x],y,1);
   end;
   2:
   begin
    read(x,y);
    update(1,n,tid[x],mx[x],y,1);
   end;
   3:
   begin
    read(x);
    writeln(querys(x));
   end;
  end;
 end;

 close(input);
 close(output);
end.