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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【vijos】【树链剖分】【小白逛公园加强版】  

2014-03-03 17:46:15|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    咱会告诉乃咱是偷懒直接复制gss7的贴上去的么...然后RE或者WA两次..才发现输出格式不对...
================================

program spojgss7;
const maxn=100010;
type
  edge=record
  v,pre:longint;
  end;

  node=record
  new,l,r,a,b:longint;
  lmax,rmax,maxx,sum:int64;
  end;

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

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;

procedure maintain(x:longint);
begin
  with t[x] do
   begin
     sum:=t[l].sum+t[r].sum;
     lmax:=max(t[l].lmax,t[l].sum+t[r].lmax);
     rmax:=max(t[r].rmax,t[r].sum+t[l].rmax);
     maxx:=max(t[l].maxx,t[r].maxx);
     maxx:=max(maxx,t[l].rmax+t[r].lmax);
     maxx:=max(maxx,lmax);
     maxx:=max(maxx,rmax); 
   end;
end;

procedure release(x:longint);
begin
  with t[x] do
   begin
     if new=maxn then exit;
     t[l].new:=new;
     t[l].sum:=(t[l].b-t[l].a)*new;
     if new>0 then
      begin
        t[l].maxx:=t[l].sum;
        t[l].lmax:=t[l].sum;
        t[l].rmax:=t[l].sum;
      end
     else
      begin
        t[l].maxx:=new;
        t[l].lmax:=new;
        t[l].rmax:=new;
      end;
     t[r].new:=new;
     t[r].sum:=(t[r].b-t[r].a)*new;
     if new>0 then
      begin
        t[r].maxx:=t[r].sum;
        t[r].lmax:=t[r].sum;
        t[r].rmax:=t[r].sum;
      end
     else
      begin
        t[r].maxx:=new;
        t[r].lmax:=new;
        t[r].rmax:=new;
      end;
     new:=maxn;
   end;
end;

procedure build(l,r:longint);
var mid,now:longint;
begin
  inc(tot);
  now:=tot;
  t[now].a:=l;t[now].b:=r;
  t[now].new:=maxn;
  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].maxx:=seg[r];
     t[now].lmax:=seg[r];
     t[now].rmax:=seg[r];
   end;
end;

procedure insert(l,r,x,w:longint);
var mid:longint;
begin
  if (t[x].a>=l)and(t[x].b<=r)then
   begin
     t[x].new:=w;
     t[x].sum:=(t[x].b-t[x].a)*w;
     if w>0 then t[x].maxx:=t[x].sum
            else t[x].maxx:=w;
     t[x].lmax:=t[x].maxx;
     t[x].rmax:=t[x].maxx;
     exit;
   end;
  release(x);
  mid:=(t[x].a+t[x].b)shr 1;
  if mid>l then insert(l,r,t[x].l,w);
  if mid<r then insert(l,r,t[x].r,w);
  maintain(x);
end;

procedure query(l,r,x,w:longint);
var mid:longint;
begin
  if (t[x].a>=l)and(t[x].b<=r)then
  if w=0 then
   begin
     if tot<0 then tot:=0;
     ans:=max(ans,t[x].maxx);
     ans:=max(ans,tot+t[x].lmax);
     tot:=max(tot+t[x].sum,t[x].rmax);
     ans:=max(ans,tot);
     exit;
   end
  else
   begin
     if tot<0 then tot:=0;
     ans:=max(ans,t[x].maxx);
     ans:=max(ans,tot+t[x].rmax);
     tot:=max(tot+t[x].sum,t[x].lmax);
     ans:=max(ans,tot);
     exit;
   end;
  release(x);
  mid:=(t[x].a+t[x].b)shr 1;
  if w=0 then
  begin
  if mid>l then query(l,r,t[x].l,w);
  if mid<r then query(l,r,t[x].r,w);
  end
  else
  begin
  if mid<r then query(l,r,t[x].r,w);
  if mid>l then query(l,r,t[x].l,w);
  end;
  maintain(x);
end;

procedure dfs1(x:longint);
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
  id[x]:=ln+1;
  seg[dep[x]]:=d[x];
  if son[x]=0 then
   begin
     inc(ln);
     top[ln]:=u;
     root[ln]:=tot+1;
     build(dep[u]-1,dep[x]);
   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(u,v,w:longint);
var t:longint;
begin
  while id[u]<>id[v] do
   begin
     if id[u]<id[v] then
      begin
        t:=u;u:=v;v:=t;
      end;
     insert(dep[top[id[u]]]-1,dep[u],root[id[u]],w);
     u:=f[top[id[u]]];
   end;
  if dep[u]>dep[v] then
   begin
     t:=u;u:=v;v:=t;
   end;
  insert(dep[u]-1,dep[v],root[id[u]],w);
end;

procedure ask(u,v:longint);
var tt,i:longint;
    change:boolean;
begin
  ans:=0;tot:=0;up:=0;
  change:=false;
  while id[u]<>id[v] do
   begin
     if id[u]<id[v] then
      begin
        tt:=u;u:=v;v:=tt;
        change:=not change;
      end;
     if change then
      begin
        inc(up);
        st[up]:=u;
        u:=f[top[id[u]]];
      end
     else
      begin
        query(dep[top[id[u]]]-1,dep[u],root[id[u]],1);
        u:=f[top[id[u]]];
      end;
   end;
  if change then
   begin
      tt:=u;u:=v;v:=tt;
   end;
  if dep[u]>dep[v] then query(dep[v]-1,dep[u],root[id[u]],1)
                   else query(dep[u]-1,dep[v],root[id[u]],0);
  for i:=up downto 1 do
   begin
     v:=st[i];
     u:=top[id[v]];
     query(dep[u]-1,dep[v],root[id[u]],0);
   end;
end;

procedure init;
var i,u,v,w,ch:longint;
begin
  read(n);
  for i:=1 to n do read(d[i]);
  tot:=0;
  fillchar(last,sizeof(last),0);
  for i:=1 to n-1 do
   begin
     read(u,v);
     addedge(u,v);
   end;
  tot:=0;ln:=0;
  fillchar(dep,sizeof(dep),0);
  fillchar(top,sizeof(top),0);
  fillchar(son,sizeof(son),0);
  fillchar(size,sizeof(size),0);
  fillchar(f,sizeof(f),0);
  fillchar(id,sizeof(id),0);
  dep[1]:=1;
  dfs1(1);
  dfs2(1,1);
  read(m);
  for i:=1 to m do
   begin
     read(ch);
     case ch of
       1:begin
           read(u,v);
           ask(u,v);
           write(ans,' ');
         end;
       2:begin
           read(u,v,w);
           modify(u,v,w);
         end;
       end;
   end;
   writeln;
end;

begin
  init;
end.

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

历史上的今天

评论

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

页脚

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