BZOJ3631 Squirrel - Hoblovski's Blog - 想拿Ag的蒟蒻.已经Ag滚出.
NOI2014 Day2 废话题解
BZOJ2300 Defence

BZOJ3631 Squirrel

Hoblovski posted @ 2014年8月24日 00:11 in Solutions with tags BZOJ Tarjan LCA ZKW线段树 树链剖分 , 778 阅读
题意
        给定一棵N个点的树T,以及一个1..N的排列P.
        你最开始在P[1],你需要依次走到P[2]...P[N].
        求每个点被经过几次.
 
Tag 树链剖分,LCA,Tarjan,树上差分
 
没想到现在还回来写题解.
最简单的做法是直接上树链剖分之后就是 1.链加 2.单点查询
树链剖分大法好,ZKW大法好,Pascal 暂定 Rank 1.
 
不过nodgd给出了一种近线性的做法.
转成有根树,对于之后每次链加(u,v),我们在
        u单点加1
        v单点加1
        LCA(u,v)单点减1
        Father(LCA(u,v))单点减1
然后经过次数统计子树和就可以了,正确性显然.LCA可以Tarjan搞.
但是这样会造成一点重复,我们只需要对于u in P[2..N],把u的答案减1即可.
 
以下是树链剖分大法ZKW大法的代码.
program bzoj3631;
  
type tnode=record
        n,next:longint;
     end;
     snode=record
        n,t1:longint;
     end;
  
const maxn=300017;
  
var g,dep,size,fa,son,top,pos,a:array[0..maxn] of longint;
    t:array[0..maxn*5] of longint;
    mem:array[0..maxn shl 1] of tnode;
    v:array[0..maxn] of boolean;
    s:array[0..maxn] of snode;
    n,m,memsize,segsize,rer,zkw:longint;
  
procedure insnbs(u,v:longint);
begin
inc(memsize); with mem[memsize] do begin
        n:=v; next:=g[u];
end; g[u]:=memsize;
inc(memsize); with mem[memsize] do begin
        n:=u; next:=g[v];
end; g[v]:=memsize;
end;
  
procedure zkwst_init(n:longint);        begin
zkw:=1; while zkw<n+2 do zkw:=zkw<<1;   end;
  
procedure add(l,r:longint);
begin
inc(l,zkw-1); inc(r,zkw+1);
while l xor r<>1 do begin
        if l and 1=0 then inc(t[l xor 1]);
        if r and 1=1 then inc(t[r xor 1]);
        l:=l>>1; r:=r>>1;
end;
end;
  
procedure dfs1(u:longint);
var head:longint;
begin
fillchar(v,sizeof(v),0); dep[u]:=1; fa[u]:=0;
rer:=1; s[rer].n:=u; s[rer].t1:=g[u]; v[u]:=true;
while rer>0 do begin head:=s[rer].n;
        while (s[rer].t1<>0)and(v[mem[s[rer].t1].n]) do s[rer].t1:=mem[s[rer].t1].next;
        if s[rer].t1=0 then begin
                inc(size[head]);                        inc(size[fa[head]],size[head]);
                if (son[fa[head]]=0)or(size[head]>size[son[fa[head]]]) then
                        son[fa[head]]:=head;
                dec(rer);
        end else begin
                inc(rer);                               s[rer].n:=mem[s[rer-1].t1].n;
                s[rer].t1:=g[s[rer].n];                 v[s[rer].n]:=true;
                dep[s[rer].n]:=dep[head]+1;             fa[s[rer].n]:=head;
        end;
end;
end;
  
procedure dfs2(u:longint);
var head:longint;
begin
fillchar(v,sizeof(v),0); top[u]:=u; segsize:=1; pos[u]:=segsize;
rer:=1; s[rer].n:=u; s[rer].t1:=g[u]; v[u]:=true;
while rer>0 do begin head:=s[rer].n;
        while (s[rer].t1<>0)and(v[mem[s[rer].t1].n]) do s[rer].t1:=mem[s[rer].t1].next;
        if (son[head]<>0)and(not v[son[head]]) then begin
                inc(rer);                               s[rer].n:=son[head];
                s[rer].t1:=g[s[rer].n];                 v[s[rer].n]:=true;
                top[s[rer].n]:=top[head];               inc(segsize);
                pos[s[rer].n]:=segsize;
        end else if s[rer].t1=0 then dec(rer) else begin
                inc(rer);                               s[rer].n:=mem[s[rer-1].t1].n;
                s[rer].t1:=g[s[rer].n];                 v[s[rer].n]:=true;
                top[s[rer].n]:=s[rer].n;                inc(segsize);
                pos[s[rer].n]:=segsize;
        end;
end;
end;
  
procedure pthadd(u,v:longint);
begin
while top[u]<>top[v] do
        if dep[top[u]]>dep[top[v]] then begin
                add(pos[top[u]],pos[u]); u:=fa[top[u]];
        end else begin
                add(pos[top[v]],pos[v]); v:=fa[top[v]];
        end;
if dep[u]<dep[v] then add(pos[u],pos[v])
                 else add(pos[v],pos[u]);
end;
  
procedure init;
var i,j,u,v:longint;
begin
readln(n); for i:=1 to n do read(a[i]); readln;
zkwst_init(n); for i:=1 to n-1 do begin
        readln(u,v); insnbs(u,v);
end; dfs1(1); dfs2(1); for i:=2 to n do t[zkw+pos[a[i]]]:=-1;
end;
  
procedure work;
var i,j:longint;
begin
for i:=1 to n-1 do pthadd(a[i],a[i+1]);
for i:=1 to zkw-1 do begin
        inc(t[i<<1],t[i]); inc(t[i<<1+1],t[i]);
end;
for i:=1 to n do writeln(t[pos[i]+zkw]);
end;
  
begin
init;
work;
end.

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter