注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1036】【ZJOI2008】【树的统计】  

2014-03-02 14:16:04|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   裸树链剖分不解释,link-cut-tree也可以做...
   练模板题。
  一次AC咩~
  另外 BZOJ 竟然不支持 左移符 <<,结果 CE了三次...
========================================

program bzoj1036;
const maxn=60010;

type edge=record
     v,pre:longint;
     end;

     node=record
     a,b,l,r,max:longint;
     sum:int64;
     end;

var e:array[0..maxn]of edge;
    last,seg,son,f,dep,id,size,top,d,root:array[0..maxn]of longint;
    tot,ln,n,m:longint;
    t:array[0..maxn shl 1]of node;

procedure addedge(u,v:longint); {读入树}
begin
  inc(tot);
  e[tot].v:=v;
  e[tot].pre:=last[u];
  last[u]:=tot;
  inc(tot);
  e[tot].v:=u;
  e[tot].pre:=last[v];
  last[v]:=tot;
end;

function max(a,b:longint):longint; {不解释..}
begin
  if a>b then exit(a) else exit(b);
end;

function max(a,b:int64):int64;
begin
  if a>b then exit(a) else exit(b);
end;

procedure maintain(x:longint); {线段树部分}
begin
   t[x].max:=max(t[t[x].l].max,t[t[x].r].max);
   t[x].sum:=t[t[x].l].sum+t[t[x].r].sum;
end;

procedure build(l,r:longint); {建立树}
var now,mid:longint;
begin
  inc(tot);
  now:=tot;
  t[now].a:=l;
  t[now].b:=r;
  if l+1<r then
   begin
     mid:=(l+r)shr 1;
     t[now].l:=tot+1;build(l,mid);
     t[now].r:=tot+1;build(mid,r);
     maintain(now);
   end
  else
   begin
     t[now].sum:=seg[r];
     t[now].max:=t[now].sum;
   end;
end;

procedure insert(l,r,x,d:longint); {修改}
var mid:longint;
begin
  if (t[x].a>=l)and(t[x].b<=r)then
   begin
     t[x].sum:=d;
     t[x].max:=d;
     exit;
   end;
  mid:=(t[x].a+t[x].b)shr 1;
  if mid>l then insert(l,r,t[x].l,d);
  if mid<r then insert(l,r,t[x].r,d);
  maintain(x);
end;

function query(l,r,x,w:longint):int64; {询问,w=0询问最大值,w=1询问和}
var mid:longint;ans:int64;
begin
  if (t[x].a>=l)and(t[x].b<=r)then
     if w=0 then exit(t[x].max)
            else exit(t[x].sum);
  mid:=(t[x].a+t[x].b)shr 1;
  if w=0 then
   begin
     ans:=-maxlongint;
     if mid>l then ans:=max(ans,query(l,r,t[x].l,w));
     if mid<r then ans:=max(ans,query(l,r,t[x].r,w));
   end
  else
   begin
     ans:=0;
     if mid>l then ans:=ans+query(l,r,t[x].l,w);
     if mid<r then ans:=ans+query(l,r,t[x].r,w);
   end;
  exit(ans);
end;

procedure dfs1(x:longint); {第一次dfs求出dep,f,son,size等信息}
var tmp:longint;
begin
  tmp:=last[x];
  size[x]:=1;
  while tmp<>0 do
   begin
     if e[tmp].v<>f[x] then
      begin
        f[e[tmp].v]:=x;
        dep[e[tmp].v]:=dep[x]+1;
        dfs1(e[tmp].v);
        size[x]:=size[x]+size[e[tmp].v];
        if size[son[x]]<size[e[tmp].v] then
          son[x]:=e[tmp].v;
      end;
     tmp:=e[tmp].pre;
   end;
end;

procedure dfs2(x,u:longint); {第二次开始树链剖分}
var tmp:longint;
begin
  seg[dep[x]]:=d[x];
  id[x]:=ln+1;
  if son[x]=0 then
   begin
     inc(ln);
     root[ln]:=tot+1;
     build(dep[u]-1,dep[x]);
     top[ln]:=u;
   end
  else
    dfs2(son[x],u);
  tmp:=last[x];
  while tmp<>0 do
   begin
     if (id[e[tmp].v]=0)then
        dfs2(e[tmp].v,e[tmp].v);
     tmp:=e[tmp].pre;
   end;
end;

procedure modify(x,w:longint); {在线段树及本身修改x的信息}
begin
  d[x]:=w;
  insert(dep[x]-1,dep[x],root[id[x]],w);
end;

function ask(u,v,w:longint):longint; {询问u到v路径的问题,w=0代表最大值,w=1代表和}
var t:longint;
    ans:int64;
begin
  if w=0 then ans:=-maxlongint
         else ans:=0;
  while id[u]<>id[v] do
   begin
     if id[u]<id[v] then
      begin
        t:=u;u:=v;v:=t;
      end;
     if u=top[id[u]] then
      if w=0 then ans:=max(ans,d[u])
             else ans:=ans+d[u]
     else
     if w=0 then ans:=max(ans,query(dep[top[id[u]]]-1,dep[u],root[id[u]],w))
            else ans:=ans+query(dep[top[id[u]]]-1,dep[u],root[id[u]],w);
     u:=f[top[id[u]]];
   end;
  if u=v then
    if w=0 then ans:=max(ans,d[u])
           else ans:=ans+d[u]
    else
     begin
       if dep[u]>dep[v] then
        begin
          t:=u;u:=v;v:=t;
        end;
       if w=0 then ans:=max(ans,query(dep[u]-1,dep[v],root[id[u]],w))
              else ans:=ans+query(dep[u]-1,dep[v],root[id[u]],w);
     end;
  exit(ans);
end;

procedure init; {总过程}
var i,u,v:longint;
    ch:char;
begin
  read(n);
  fillchar(last,sizeof(last),0);
  tot:=0;
  for i:=1 to n-1 do
   begin
     read(u,v);
     addedge(u,v);
   end;
  for i:=1 to n do
   read(d[i]);
  fillchar(dep,sizeof(dep),0);
  fillchar(size,sizeof(size),0);
  fillchar(son,sizeof(son),0);
  fillchar(f,sizeof(f),0);
  fillchar(id,sizeof(id),0);
  ln:=0;
  dep[1]:=1;
  dfs1(1);
  dfs2(1,1);
  readln(m);
  for i:=1 to m do
   begin
     read(ch,ch);
     case ch of
       'M':begin
             readln(ch,ch,u,v);
             writeln(ask(u,v,0));
           end;
       'S':begin
             readln(ch,ch,u,v);
             writeln(ask(u,v,1));
           end;
       'H':begin
             readln(ch,ch,ch,ch,u,v);
             modify(u,v);
           end;
     end;
   end;
end;

begin
  init;
end.






  评论这张
 
阅读(29)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018