笔芯吧 关注：5,893贴子：285,982
Amami
树链剖分的实现步骤：
1、第一趟dfs，找重（zhong）边，顺便确定每个节点的父亲、重儿子、深度和size（详见ppt），同时把无根树转化为有根树
2、第二趟dfs，拉出重链，记录top，构建新树同时反向标记
3、构建线段树
4、解决区间修改和查找问题：将两个点尽量向同一条重链上靠，深度大的优先；详见代码
树链剖分真是丧心病狂，代码长度无压力破200
下面贴上例题：bzoj 1036
var
n,i,x,y,m,edgenum,time:longint;
a,head,vet,next,fa,dep,size,flag,tid,son,top,pre,tree_max,tree_sum,isok:array[1..200010]of longint;
st:string;
procedure addedge(x,y:longint);
begin
inc(edgenum);
vet[edgenum]:=y;
next[edgenum]:=head[x];
head[x]:=edgenum;
end;
procedure dfs1(u,father,depth:longint);
var
e,v,maxsize:longint;
begin
fa[u]:=father; dep[u]:=depth;
size[u]:=1; maxsize:=0; son[u]:=0;
flag[u]:=1;
e:=head[u];
while e<>0 do
begin
v:=vet[e];
if flag[v]=0 then
begin
isok[e]:=1;
dfs1(v,u,depth+1);
size[u]:=size[u]+size[v];
if size[v]>maxsize then
begin
maxsize:=size[v];
son[u]:=v;
end;
end;
e:=next[e];
end;
end;
procedure dfs2(u
1、第一趟dfs，找重（zhong）边，顺便确定每个节点的父亲、重儿子、深度和size（详见ppt），同时把无根树转化为有根树
2、第二趟dfs，拉出重链，记录top，构建新树同时反向标记
3、构建线段树
4、解决区间修改和查找问题：将两个点尽量向同一条重链上靠，深度大的优先；详见代码
树链剖分真是丧心病狂，代码长度无压力破200
下面贴上例题：bzoj 1036
var
n,i,x,y,m,edgenum,time:longint;
a,head,vet,next,fa,dep,size,flag,tid,son,top,pre,tree_max,tree_sum,isok:array[1..200010]of longint;
st:string;
procedure addedge(x,y:longint);
begin
inc(edgenum);
vet[edgenum]:=y;
next[edgenum]:=head[x];
head[x]:=edgenum;
end;
procedure dfs1(u,father,depth:longint);
var
e,v,maxsize:longint;
begin
fa[u]:=father; dep[u]:=depth;
size[u]:=1; maxsize:=0; son[u]:=0;
flag[u]:=1;
e:=head[u];
while e<>0 do
begin
v:=vet[e];
if flag[v]=0 then
begin
isok[e]:=1;
dfs1(v,u,depth+1);
size[u]:=size[u]+size[v];
if size[v]>maxsize then
begin
maxsize:=size[v];
son[u]:=v;
end;
end;
e:=next[e];
end;
end;
procedure dfs2(u
