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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Hdu4010】【Link-cut-tree模板题】【Query on the trees】  

2014-04-21 20:12:33|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   最近の几道题太凶残了【比如FFT算贡献什么的...还没有想清楚T T】,所以咱就写一道模板题涨涨信心= =【可悲的涨信心】
   题目大意:
   维护森林,点有点权,支持以下操作:
   1)link(a,b):如果a,b不在一个子树,则连接a,b。
   2)cut(a,b),如果a,b在一个子树,a!=b,则以a为根,切断b与其父亲。
   3)Modify(a,b,w),如果a,b在一个子树,则以a,b的路径的点的点权整体加上w. 
   4)Query(a,b),如果a,b在一个子树,询问a,b路径上的点权最大值。  
   0.0比较基础的link-cut-tree的操作额...所以就这样了。

   看有木有时间...准备来探讨了一下,splay是zig-zag分开写快还是 一个rotate快....
   这次用P交了Hdu终于没有各种奇怪的错误了=w=

   然后就是一些细节额...应该没有人像咱一样傻叉到连模板都打不对了吧...
   1)这里找根节点的那个操作又一次像上次一样忘记下放标记了...TLE一次= =。
   2)另外一个错误是cut里面,翻转根之后咱是直接用a的父亲access上去,再把a的父亲变成0完事,但是这个是不对的饿...如果翻转的根是a的后代的话,那么a的父亲就不是原来那一位的..... = =所以得先access掉a,然后这个时候它的父亲必然在左子树,这个时候把左子树断掉即可。
   3)致PE的朋友们0.0...注意每一组数据都要输出一行空格,【包括最后一组数据】【还特意加了特判要求最后一组数据不输出空格的啊啊啊QAQ】
   4)注意 0 号节点的信息要始终为0,包括a,add,maxx都为0。即在下放标记的时候注意要判断儿子是否为0。
   5)像将某个点打了个标记之后,要当场下放掉,咱的link-cut-tree可能会由于没能即时下放而导致最上面的信息可能会影响【比如这个时候断掉某个儿子】【这个时候就要把标记即时下放】。

====================

program hdu4010;
const maxn=300010;
type node=record
     son:array[0..1]of longint;
     f,add,maxx,a:longint;
     flip:boolean;
     end;
     edge=record
     v,pre:longint;
     end;

var t:array[0..maxn]of node;
    root:array[0..maxn]of boolean;
    last:array[0..maxn]of longint;
    e:array[0..maxn*2]of edge;
    n,tot,tt:longint;

function wh(p:longint):longint;
begin
  if t[t[p].f].son[1]=p then wh:=1
  else wh:=0;
end;

function max(a,b:longint):longint;
begin
  if a>b then max:=a else max:=b;
end;

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;

procedure swap(var a,b:longint);
var t:longint;
begin
  t:=a;a:=b;b:=t;
end;

procedure maintain(p:longint);
begin
  t[p].maxx:=max(max(t[t[p].son[0]].maxx,t[t[p].son[1]].maxx),t[p].a);
end;

procedure push(p:longint);
var i,j:longint;
begin
  if t[p].add<>0 then
   begin
     i:=t[p].son[0];j:=t[p].son[1];
     if i<>0 then inc(t[i].add,t[p].add);
     if j<>0 then inc(t[j].add,t[p].add);
     if i<>0 then inc(t[i].a,t[p].add);
     if j<>0 then inc(t[j].a,t[p].add);
     if i<>0 then inc(t[i].maxx,t[p].add);
     if j<>0 then inc(t[j].maxx,t[p].add);
     t[p].add:=0;
   end;
  if t[p].flip then
   begin
     i:=t[p].son[0];j:=t[p].son[1];
     t[i].flip:=not t[i].flip;
     t[j].flip:=not t[j].flip;
     swap(t[i].son[0],t[i].son[1]);
     swap(t[j].son[0],t[j].son[1]);
     t[p].flip:=false;
   end;
end;

procedure rotate(p:longint);
var w,y:longint;
begin
  with t[p] do
   begin
     y:=f;
     w:=wh(p);
     f:=t[y].f;
     if not root[y] then
       t[t[y].f].son[wh(y)]:=p;
     t[son[w xor 1]].f:=y;
     t[y].son[w]:=son[w xor 1];
     son[w xor 1]:=y;
     t[y].f:=p;
     root[p]:=root[y] xor root[p];
     root[y]:=root[y] xor root[p];
     t[y].maxx:=max(max(t[t[y].son[0]].maxx,t[t[y].son[1]].maxx),t[y].a);
     maxx:=max(max(t[son[0]].maxx,t[son[1]].maxx),a)
   end;
end;

procedure splay(p:longint);
begin
  push(p);
  while not root[p] do
   if root[t[p].f] then
    begin
      push(t[p].f);
      push(p);
      rotate(p);
    end
   else
    begin
      push(t[t[p].f].f);
      push(t[p].f);
      push(p);
      if wh(p) xor wh(t[p].f)=0 then rotate(t[p].f)
                                else rotate(p);
      rotate(p);
    end;
end;

procedure access(p:longint);
var y:longint;
begin
  splay(p);
  root[t[p].son[1]]:=true;
  t[p].son[1]:=0;
  maintain(p);
  while t[p].f<>0 do
   begin
     y:=t[p].f;
     splay(y);
     root[t[y].son[1]]:=true;
     root[p]:=false;
     t[y].son[1]:=p;
     maintain(y);
     splay(p);
   end;
end;


procedure evert(p:longint);
begin
  access(p);
  t[p].flip:=not t[p].flip;
  swap(t[p].son[0],t[p].son[1]);
  push(p);
end;

function findroot(u:longint):longint;
begin
  access(u);
  while t[u].son[0]<>0 do
   begin
    push(u);
    u:=t[u].son[0];
   end;
  push(u);
  findroot:=u;
end;

procedure link(u,v:longint);
begin
  if (u=v)or(findroot(u)=findroot(v)) then
   begin
     writeln(-1);
     exit;
   end;
  evert(v);
  t[v].f:=u;
end;

procedure cut(u,v:longint);
begin
  if (u=v)or(findroot(u)<>findroot(v)) then
   begin
     writeln(-1);
     exit;
   end;
  evert(u);
  access(v);
  root[t[v].son[0]]:=true;
  t[t[v].son[0]].f:=0;
  t[v].son[0]:=0;
  maintain(v);
end;

procedure modify(w,u,v:longint);
begin
  if findroot(u)<>findroot(v) then
   begin
     writeln(-1);
     exit;
   end;
  evert(u);
  access(v);
  inc(t[v].add,w);
  inc(t[v].a,w);
  inc(t[v].maxx,w);
  push(v);
end;

procedure query(u,v:longint);
begin
  if findroot(u)<>findroot(v) then
   begin
     writeln(-1);
     exit;
   end;
  evert(u);
  access(v);
  writeln(t[v].maxx);
end;

procedure dfs(u,fa:longint);
var tmp:longint;
begin
  t[u].f:=fa;
  tmp:=last[u];
  while tmp<>0 do
   begin
     if e[tmp].v<>fa then dfs(e[tmp].v,u);
     tmp:=e[tmp].pre;
   end;
end;

procedure init;
var i,u,v,w,q:longint;
begin
  read(n);
  t[0].maxx:=-1;tot:=0;
  fillchar(root,sizeof(root),true);
  fillchar(last,sizeof(last),0);
  for i:=1 to n do
   begin
     t[i].f:=0;
     t[i].son[0]:=0;
     t[i].son[1]:=0;
     t[i].flip:=false;
   end;
  for i:=1 to n-1 do
   begin
     read(u,v);
     addedge(u,v);
   end;
  dfs(1,0);
  for i:=1 to n do
   begin
     read(w);
     t[i].a:=w;
     t[i].maxx:=w;
     t[i].add:=0;
   end;
  read(q);
  for i:=1 to q do
    begin
      read(w);
      case w of
      1:begin
          read(u,v);
          link(u,v);
        end;
      2:begin
          readln(u,v);
          cut(u,v);
        end;
      3:begin
          readln(w,u,v);
          modify(w,u,v);
        end;
      4:begin
          readln(u,v);
          query(u,v);
        end;
      end;
    end;
end;

begin
  tt:=1;
  while not seekeof do
   begin
    init;
    writeln;
   end;
end.

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

历史上的今天

评论

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

页脚

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