bzoj1036[ZJOI2008]树的统计Count【树链剖分】

  • 内容
  • 评论
  • 相关

第一道树链剖分题~


题目点击这里

就是树链剖分的裸题啦~直接套模板就行,关于树链剖分的讲解点这里


代码:

type
  node=record
         l,r,max,sum:longint;
       end;
var
  t:array[1..65536]of node;
  v,next:array[1..60000]of longint;
  a,d,num,dep,top,f,son,tree,pre:array[1..30000]of longint;
  n,m,i,j,k,p,q,tot:longint;
  c:char;
function max(a,b:longint):longint;
begin
  if a>b then exit(a) else exit(b);
end;
procedure adde(uu,vv:longint);
begin
  inc(k);
  v[k]:=vv;
  next[k]:=a[uu];
  a[uu]:=k;
  inc(k);
  v[k]:=uu;
  next[k]:=a[vv];
  a[vv]:=k;
end;
procedure dfs1(k,fa,d:longint);
var
  i:longint;
begin
  dep[k]:=d;
  f[k]:=fa;
  num[k]:=1;
  i:=a[k];
  while i<>0 do
  begin
    if v[i]<>fa then
    begin
      dfs1(v[i],k,d+1);
      num[k]:=num[k]+num[v[i]];
      if (son[k]=0) or (num[v[i]]>num[son[k]]) then son[k]:=v[i];
    end;
    i:=next[i];
  end;
end;
procedure dfs2(k,n:longint);
var
  i:longint;
begin
  top[k]:=n;
  inc(tot);
  tree[k]:=tot;
  pre[tree[k]]:=k;
  if son[k]=0 then exit;
  dfs2(son[k],n);
  i:=a[k];
  while i<>0 do
  begin
    if (v[i]<>son[k]) and (v[i]<>f[k]) then dfs2(v[i],v[i]);
    i:=next[i];
  end;
end;
procedure build(k,l,r:longint);
var
  mid:longint;
begin
  t[k].l:=l;
  t[k].r:=r;
  if l=r then
  begin
    t[k].sum:=d[pre[l]];
    t[k].max:=d[pre[r]];
    exit;
  end;
  mid:=(l+r) shr 1;
  build(k shl 1,l,mid);
  build(k shl 1 or 1,mid+1,r);
  t[k].sum:=t[k shl 1].sum+t[k shl 1 or 1].sum;
  t[k].max:=max(t[k shl 1].max,t[k shl 1 or 1].max);
end;
function qqmax(k,l,r:longint):longint;
var
  mid,ans:longint;
begin
  if (t[k].l>=l) and (t[k].r<=r) then exit(t[k].max);
  mid:=(t[k].l+t[k].r) shr 1;
  ans:=-2147483647;
  if l<=mid then ans:=max(ans,qqmax(k shl 1,l,r));
  if r>mid then ans:=max(ans,qqmax(k shl 1 or 1,l,r));
  t[k].sum:=t[k shl 1].sum+t[k shl 1 or 1].sum;
  t[k].max:=max(t[k shl 1].max,t[k shl 1 or 1].max);
  exit(ans);
end;
function qmax(var p,q:longint):longint;
var
  x,y,ans,t:longint;
begin
  x:=top[p];
  y:=top[q];
  ans:=-2147483647;
  while x<>y do
  begin
    if dep[x]<dep[y] then
    begin
      t:=x;
      x:=y;
      y:=t;
      t:=p;
      p:=q;
      q:=t;
    end;
    ans:=max(ans,qqmax(1,tree[x],tree[p]));
    p:=f[x];
    x:=top[p];
  end;
  if dep[p]>dep[q] then
  ans:=max(ans,qqmax(1,tree[q],tree[p]))
  else ans:=max(ans,qqmax(1,tree[p],tree[q]));
  exit(ans);
end;
function qqsum(k,l,r:longint):longint;
var
  mid,ans:longint;
begin
  if (t[k].l>=l) and (t[k].r<=r) then exit(t[k].sum);
  mid:=(t[k].l+t[k].r) shr 1;
  ans:=0;
  if l<=mid then ans:=ans+qqsum(k shl 1,l,r);
  if r>mid then ans:=ans+qqsum(k shl 1 or 1,l,r);
  t[k].sum:=t[k shl 1].sum+t[k shl 1 or 1].sum;
  t[k].max:=max(t[k shl 1].max,t[k shl 1 or 1].max);
  exit(ans);
end;
function qsum(var p,q:longint):longint;
var
  x,y,ans,t:longint;
begin
  x:=top[p];
  y:=top[q];
  ans:=0;
  while x<>y do
  begin
    if dep[x]<dep[y] then
    begin
      t:=x;
      x:=y;
      y:=t;
      t:=p;
      p:=q;
      q:=t;
    end;
    ans:=ans+qqsum(1,tree[x],tree[p]);
    p:=f[x];
    x:=top[p];
  end;
  if dep[p]>dep[q] then
  ans:=ans+qqsum(1,tree[q],tree[p])
  else ans:=ans+qqsum(1,tree[p],tree[q]);
  exit(ans);
end;
procedure update(k,x,o:longint);
var
  mid:longint;
begin
  if t[k].l=t[k].r then
  begin
    t[k].sum:=t[k].sum+o;
    t[k].max:=t[k].max+o;
    exit;
  end;
  mid:=(t[k].l+t[k].r) shr 1;
  if x<=mid then update(k shl 1,x,o) else update(k shl 1 or 1,x,o);
  t[k].sum:=t[k shl 1].sum+t[k shl 1 or 1].sum;
  t[k].max:=max(t[k shl 1].max,t[k shl 1 or 1].max);
end;
begin
  readln(n);
  for i:=1 to n-1 do
  begin
    readln(p,q);
    adde(p,q);
  end;
  for i:=1 to n do
  read(d[i]);
  dfs1(1,0,1);
  dfs2(1,1);
  build(1,1,n);
  readln(m);
  repeat
    dec(m);
    read(c);
    read(c);
    if c='M' then
    begin
      for i:=1 to 3 do read(c);
      readln(p,q);
      writeln(qmax(p,q));
    end;
    if c='S' then
    begin
      for i:=1 to 3 do read(c);
      readln(p,q);
      writeln(qsum(p,q));
    end;
    if c='H' then
    begin
      for i:=1 to 5 do read(c);
      readln(p,q);
      update(1,tree[p],q-d[p]);
      d[p]:=q;
    end;
  until m=0;
end.

之前有几个小地方有点问题调试了一会。。。

评论

0条评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据