基本定义

方法

常见作用

LCA代码

经典题目

CPP标程

基本定义

树链剖分:

目标: 一颗树,,将其划分为若干条链,,,每个点属于且仅属于一条链,,,

划分的方法很多,,,不过按某种方法划分却有一条很好的性质,,,任意一点到根结点的路径上的链的个数不超过logn条,,,

于是如果能把问题转化为维护点到根结点路径的问题,,再用线性结构维护每条链,,那么复杂度就是 维护链的复杂度*logn,,很优秀了,,,

方法

常见的路径剖分的方法是轻重边剖分，即把树中的边分为轻重两部分，方法：设SZ[i]为以i为根的子树的大小（结点总数），则若点x不是叶结点，则其子结点中SZ值最大的（注意，有多个SZ值最大的子结点应任选一个，只能选一个，防止出现重链相交，引发歧义）点y，边(x, y)称为重边，其余的边都是轻边。首尾相连的重边称为重链（注意一定是自上而下的），则一个很显然的性质是：从根结点到任意点i路径上的轻边与重链的总数都不会超过O(log2N)。然后，对每条重链上的边建立线段树，每当遇到改值操作，若是轻边就直接改，若是重边就在线段树里改；遇到找x、y路径上边权最大值的操作，只要找到LCA(x, y)，然后从x、y开始沿着树边上溯到LCA(x, y)处，对于中间的每条轻边和重链（线段树内）导出最大值即可。

常见作用

求LCA：可以对整棵树作深度优先遍历，记下每个遇到的点（包括向上的和向下的）的编号，形成一个长度为2(N-1)的序列A，然后，找到点x、y在A中的第一次出现的位置（设为FF[x]和FF[y]），则A[FF[x]..FF[y]]中的深度最小的点的编号就是LCA(x, y)，显然这需要RMQ。

具体步骤：

（1）输入部分：建立无根树；

（2）预处理部分：分为6步：

<1>利用BFS将无根树转化为有根树，同时求出有根树中点i（根结点除外）到其父结点的边的编号（设为FA[i]）以及点i的深度（设为DEP[i]）；

<2>自底向上计算每个点的SZ值，同时划分轻重边（对于有根树中的每条边设立Z域，Z=1为重边，Z=0为轻边）；

<3>求出重链，建立线段树：

求重链的方法：由于重链只会在叶结点处结束，因此从每个叶结点开始上溯，直到上溯到根或者遇到轻边为止。为了方便，需要对每个结点i记录以下4个值：UP[i]表示点i所在重链最顶上的那个结点的编号；ord[i]表示点i是其所在重链的上起第几个点（从0开始）；tot[i]表示点i所在重链上有几个结点；root[i]表示点i所在重链建成的线段树的编号（这样经常写的opr(0, n-1, root)就可以表示成opr(0, tot[i]-1, root[i])）。求出重链以后，对沿途经历的所有边的权值倒序写入数组W0，再对数组W0建线段树即可。考虑到不同线段树的大小可能不同，这里采用压缩处理，这样就需要记录每个点的lch、rch编号（见代码）；

<4>对树进行DFS遍历，求出序列A；

<5>求出序列A的倍增最小值，存放在A0[][]里（注意：A和A0中记载的都是编号，而判定大小的关键字是深度）；

<6>求出LOG[i]=log2i（下取整）；

（3）执行部分：对于询问操作，求LCA，不断上溯，对于重链在线段树里找即可，注意线段树的左右端点，尤其是当UP在LCA之上时，只能上溯到LCA处。

划分方法:

先预处理出以每个节点为根的子树所包含的节点的总数,即size,,

然后 每个节点和其size最大的出边(不含父亲方向) 连边(红色边),,,

这样由红色边连在一起的就是一条链,,,,然后剩余的单个的点也看作一条链,,,,

图中共有5条链,,,

1-6-8-10,,,,2-3-4,,,5,,,,7,,,,9

这样我们便达到了目的,,每个点仅属于一条链,,,

编程办法,,,怎么简单怎么来

模拟递归栈,,,

计算机的速度越来越高,,,使题目的数据越来越大,,这样用递归的办法就越来越容易暴栈,,

一个10万的点的链进行递归深搜,,,就几乎一定会暴栈,,,

模拟栈的方法:

参数,,,,如果只有一个参数,,用一个数组既可,,,有多个参数就用结构体存储每个参数,,

自底向上的更新,,,如果没有这种更新,,,直接写既可,,如果有的话,,,每个节点被取出2次,,,第一次不弹栈,,第二次弹掉,,,第一次将子节点入栈,,并处理自顶向下的更新,,,第二次处理自底向上的更新,,,,

LCA代码

编程注意事项：建代码中标Attention的地方。

代码（我这个代码常数巨大，时间达3.61s，不知是肿么搞得，神犇来看一下啊囧）：

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

using namespace std;

#define re(i, n) for (int i=0; i<n; i++)

#define re1(i, n) for (int i=1; i<=n; i++)

#define re2(i, l, r) for (int i=l; i<r; i++)

#define re3(i, l, r) for (int i=l; i<=r; i++)

#define rre(i, n) for (int i=n-1; i>=0; i--)

#define rre1(i, n) for (int i=n; i>0; i--)

#define rre2(i, r, l) for (int i=r-1; i>=l; i--)

#define rre3(i, r, l) for (int i=r; i>=l; i--)

const int MAXN = 10001, MAXS = 20, INF = ~0U >> 2;

struct edge {

int a, b, w, pre, next;

bool Z;

} E0[MAXN << 2], E[MAXN + MAXN + 1];

struct node {

int maxv, lch, rch;

} T[MAXN << 2];

int n, m0, m, N, _a[MAXN], _b[MAXN], FA[MAXN], Q[MAXN], SZ[MAXN], DEP[MAXN], W0[MAXN], UP[MAXN], ord[MAXN], root[MAXN], tot[MAXN];

int n1, stk[MAXN], st[MAXN], A[MAXN << 2], A0[MAXN << 2][MAXS], FF[MAXN], LOG[MAXN << 2], l0, r0, x0, res;

bool vst[MAXN];

void init_d()

{

re(i, n) E0[i].pre = E0[i].next = E[i].pre = E[i].next = i;

m0 = m = n;

}

void add_edge0(int a, int b, int w)

{

E0[m0].a = a; E0[m0].b = b; E0[m0].w = w; E0[m0].pre = E0[a].pre; E0[m0].next = a; E0[a].pre = m0; E0[E0[m0].pre].next = m0++;

E0[m0].a = b; E0[m0].b = a; E0[m0].w = w; E0[m0].pre = E0[b].pre; E0[m0].next = b; E0[b].pre = m0; E0[E0[m0].pre].next = m0++;

}

void add_edge(int a, int b, int w)

{

E[m].a = a; E[m].b = b; E[m].w = w; E[m].Z = 0; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m++;

}

int mkt(int l, int r)

{

int No = ++N;

if (l == r) {

T[No].maxv = W0[l]; T[No].lch = T[No].rch = 0;

} else {

int mid = l + r >> 1, l_r = mkt(l, mid), r_r = mkt(mid + 1, r); T[No].lch = l_r; T[No].rch = r_r;

if (T[l_r].maxv >= T[r_r].maxv) T[No].maxv = T[l_r].maxv; else T[No].maxv = T[r_r].maxv;

}

return No;

}

void prepare()

{

re(i, n) vst[i] = 0; Q[0] = 0; vst[0] = 1; DEP[0] = 0; FA[0] = -1;

int i0, j0;

for (int front=0, rear=0; front<=rear; front++) {

i0 = Q[front];

for (int p=E0[i0].next; p != i0; p=E0[p].next) {

j0 = E0[p].b;

if (!vst[j0]) {add_edge(i0, j0, E0[p].w); vst[j0] = 1; Q[++rear] = j0; FA[j0] = m - 1; DEP[j0] = DEP[i0] + 1;}

}

}

int maxSZ, x, n0, root0;

rre(i, n) {

i0 = Q[i]; SZ[i0] = 1; maxSZ = 0;

for (int p=E[i0].next; p != i0; p=E[p].next) {SZ[i0] += SZ[j0 = E[p].b]; if (SZ[j0] > maxSZ) {maxSZ = SZ[j0]; x = p;}}

if (SZ[i0] > 1) E[x].Z = 1; //Attention

}

UP[0] = 0; ord[0] = 0; N = 0;

re2(i, 1, n) {

i0 = Q[i]; x = FA[i0]; if (E[x].Z) {UP[i0] = UP[E[x].a]; ord[i0] = ord[E[x].a] + 1;} else {UP[i0] = i0; ord[i0] = 0;}

if (SZ[i0] == 1 && ord[i0]) {

j0 = UP[i0]; n0 = ord[i0];

for (int j=i0; j!=j0; j=E[FA[j]].a) {tot[j] = ord[i0]; W0[--n0] = E[FA[j]].w;} tot[j0] = ord[i0]; //Attention

root0 = mkt(0, ord[i0] - 1); //Attention

for (int j=i0; j!=j0; j=E[FA[j]].a) root[j] = root0; root[j0] = root0; //Attention

}

}

re(i, n) {st[i] = E[i].next; FF[i] = -1;} stk[0] = 0; int tp = 0; n1 = 1; A[0] = FF[0] = 0;

while (tp >= 0) {

i0 = stk[tp]; x = st[i0];

if (x != i0) {

j0 = E[x].b; if (FF[j0] == -1) FF[j0] = n1; A[n1++] = j0; st[i0] = E[x].next; stk[++tp] = j0;

} else {

if (tp) A[n1++] = stk[tp - 1];

tp--;

}

}

rre(i, n1) {

A0[i][0] = A[i]; x = 1;

re2(j, 1, MAXS) if (i + (x << 1) <= n1) {

if (DEP[A0[i][j - 1]] <= DEP[A0[i + x][j - 1]]) A0[i][j] = A0[i][j - 1]; else A0[i][j] = A0[i + x][j - 1]; //Attention

x <<= 1;

} else break;

}

int _x; x = 1;

re(i, MAXS) {

_x = x << 1;

if (_x < n1) re2(j, x, _x) LOG[j] = i; else {re2(j, x, n1) LOG[j] = i; break;}

x = _x;

}

}

void opr0(int l, int r, int No)

{

if (l == l0 && r == l0) T[No].maxv = x0; else {

int mid = l + r >> 1, lch = T[No].lch, rch = T[No].rch;

if (mid >= l0) opr0(l, mid, lch);

if (mid < l0) opr0(mid + 1, r, rch);

if (T[lch].maxv >= T[rch].maxv) T[No].maxv = T[lch].maxv; else T[No].maxv = T[rch].maxv;

}

}

void opr1(int l, int r, int No)

{

if (l >= l0 && r <= r0) {

if (T[No].maxv > res) res = T[No].maxv;

} else {

int mid = l + r >> 1;

if (mid >= l0) opr1(l, mid, T[No].lch);

if (mid < r0) opr1(mid + 1, r, T[No].rch);

}

}

int main()

{

int tests, a0, b0, w0, LCA, LOG0, FF0, FF1, p0, tmp;

char ss[20], ch;

scanf("%d", &tests);

re(testno, tests) {

scanf("%d", &n); init_d();

re(i, n-1) {scanf("%d%d%d", &a0, &b0, &w0); add_edge0(--a0, --b0, w0); _a[i] = a0; _b[i] = b0;}

prepare(); ch = getchar();

while (1) {

scanf("%s", ss);

if (!strcmp(ss, "QUERY")) {

scanf("%d%d%*c", &a0, &b0); --a0; --b0;

if (a0 == b0) res = 0; else res = -INF;

FF0 = FF[a0]; FF1 = FF[b0];

if (FF0 > FF1) {tmp = FF0; FF0 = FF1; FF1 = tmp;}

LOG0 = LOG[FF1 - FF0 + 1];

if (DEP[A0[FF0][LOG0]] <= DEP[A0[FF1 - (1 << LOG0) + 1][LOG0]]) LCA = A0[FF0][LOG0]; else LCA = A0[FF1 - (1 << LOG0) + 1][LOG0];

while (a0 != LCA) {

p0 = FA[a0];

if (E[p0].Z) {

r0 = ord[a0] - 1; if (DEP[UP[a0]] >= DEP[LCA]) l0 = 0; else l0 = ord[LCA]; //Attention

if (l0 <= r0) opr1(0, tot[a0] - 1, root[a0]); //Attention

if (l0) a0 = LCA; else a0 = UP[a0];

} else {

if (E[p0].w > res) res = E[p0].w;

a0 = E[p0].a;

}

}

while (b0 != LCA) {

p0 = FA[b0];

if (E[p0].Z) {

r0 = ord[b0] - 1; if (DEP[UP[b0]] >= DEP[LCA]) l0 = 0; else l0 = ord[LCA]; //Attention

if (l0 <= r0) opr1(0, tot[b0] - 1, root[b0]); //Attention

if (l0) b0 = LCA; else b0 = UP[b0];

} else {

if (E[p0].w > res) res = E[p0].w;

b0 = E[p0].a;

}

}

printf("%d\", res);

} else if (!strcmp(ss, "CHANGE")) {

scanf("%d%d", &a0, &w0); b0 = _b[--a0]; a0 = _a[a0];

if (FA[b0] == -1 || E[FA[b0]].a != a0) {tmp = a0; a0 = b0; b0 = tmp;}

p0 = FA[b0];

if (E[p0].Z) {

l0 = ord[a0]; x0 = w0; opr0(0, tot[a0] - 1, root[a0]);

} else E[p0].w = w0;

} else break;

}

}

return 0;

}

树的路径剖分是解决树上路径的操作查询问题的有力工具，它还有一些更为强大的应用，以后再来搞……

经典题目

// 题意： 给定一颗带权树，要求实现2个操作： 1、修改边权， 2、得到2个点的路径上的最大边权值;

// 树链剖分， 经典写法， 把轻边也加入线段树;

// 卡时间的题，用read(), readchar(),读入可以加快至少1s，又多会了点东西;

// 非常精妙的dfs处理， 非常优美的遍历树链写法！

#include <cstdio>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

usingnamespacestd;

#define mpair make_pair

#define pii pair<int,int>

#define MM(a,b) memset(a,b,sizeof(a));

typedeflonglonglld;

typedefunsignedlonglongu64;

template<classT>boolup_max(T&a,constT& b){return b>a?a=b,1:0;}

template<classT>boolup_min(T&a,constT& b){return b<a?a=b,1:0;}

#define maxn 10020

#define inf -1000000000

int n,top;

structEdge{

intv,id;

Edge*next;

}*adj[maxn],edge[maxn+maxn];

voidAddedge(intu,intv,intid){

Edge*p=&edge[++top];

p->v=v, p->id=id;

p->next=adj[u];

adj[u]= p;

}

intw[maxn]; // the weight of the edge i;

intfather[maxn],d[maxn]; // the father node and the depth;

intLink[maxn]; // mark the node which edge is;

intson[maxn]; // mark which node is the next node, that them form a weighted edge;

intsonedge[maxn]; // mark the id of the edge the node that from father;

intdfs(intu,intFa,intdep,intid){

d[u]=dep,father[u]=Fa,Link[u]=id;

intsize=1,maxsize=inf;

for(Edge*p=adj[u];p;p= p->next){

intv= p->v;

if( v==Fa ) continue;

inttmp=dfs(v,u,dep+1,p->id);

size+=tmp;

if( up_max( maxsize,tmp ) ){

son[u]=v,sonedge[u]= p->id;

}

}

returnsize;

}

int N,T[3*maxn];

intpre[maxn]; // the root of the weighted edge;

intmark[maxn]; // mark the position of the edge i on segment tree;

intoppomark[maxn]; // opposite to mark[] , convenient for us to build segment tree;

voiddfs2(intu,intf){

pre[u]=f,mark[Link[u]]=++N;

oppomark[N]=Link[u];

if( !son[u] ) return;

dfs2( son[u],f ); ////////////

for(Edge*p=adj[u];p;p= p->next){

intv= p->v;

if( v==father[u] || son[u]==v ) continue; ///////////

dfs2(v,v);

}

}

voidcreate(intu,intl,intr){

if(l==r){T[u]=w[oppomark[l]];return; }

intmid= (l+r)>>1;

create( u+u,l,mid );

create( u+u+1,mid+1,r );

T[u]=max( T[u+u],T[u+u+1] );

}

voidupdate(intu,intl,intr,intpos,intval){

if(l==r){

T[u]=val; return;

}

intmid= (l+r)>>1;

if(pos<=mid) update(u+u,l,mid,pos,val);

elseupdate(u+u+1,mid+1,r,pos,val);

T[u]=max( T[u+u],T[u+u+1] );

}

intget_max(intu,intl,intr,inttl,inttr){

if(tl<=l&&r<=tr) returnT[u];

intmid= (l+r)>>1;

if( tr<=mid ) returnget_max(u+u,l,mid,tl,tr);

elseif(tl>mid) returnget_max(u+u+1,mid+1,r,tl,tr);

else{

intt1=get_max(u+u,l,mid,tl,mid);

intt2=get_max(u+u+1,mid+1,r,mid+1,tr);

returnmax( t1,t2 );

}

}

voidbuild_tree(){

w[0]=inf;

N=0;

for(inti=1;i<=n;++i) son[i]=0;

dfs(1,-1,1,0);

dfs2(1,1);

create(1,1,N);

}

/*************************** 非常好的写法 ****************************/

intread(){

charc;

while( c=getchar(),!isdigit(c) );

intr=c-'0';

while( c=getchar(),isdigit(c) ) r=r*10+c-'0';

returnr;

}

charreadchar(){

charc,r;

while( r=getchar(),!isalpha(r) );

while( c=getchar(),isalpha(c) );

returnr;

}

/*********************************************************************/

voidsolve(){

charch;

intx,y;

while( ch=readchar() ,'D'!=ch){

x=read(),y=read();

if( 'C'==ch){

update( 1,1, N,mark[x],y );

}

else{

if( x==y){

puts("0"); continue;

}

intans=inf,nx,ny;

for( ; pre[x]!=pre[y] ; x=father[nx]){

nx=pre[x],ny=pre[y];

//if( d[x]<d[y] ) swap(x,y), swap(nx,ny); /////////swap(nx,ny); we should not write like this!!!!

if( d[nx]<d[ny] ) swap(x,y),swap(nx,ny); //////// we choose the root to compare to determine move which node up;

up_max( ans,get_max( 1,1, N,mark[Link[nx]],mark[Link[x]] ) );

}

if( d[x]<d[y] ) swap(x,y);

if( x!=y )

up_max( ans,get_max( 1,1, N,mark[sonedge[y]],mark[Link[x]] ) );

printf("%d\",ans);

}

}

}

intmain()

{

intCas,i,u,v;

Cas=read();

while(Cas--){

n=read();

top=0;

MM( adj,0 );

for(i=1;i<n;++i){

u=read(),v=read(),w[i]=read();

Addedge(u,v,i);

Addedge(v,u,i);

}

build_tree();

solve();

}

}

CPP标程

<PRE class=cpp name="code">/*</PRE>

<PRE class=cpp name="code">节点的标号从1开始

*/

#include <cstdio>

#include <algorithm>

using namespace std;

const int N = 10000; //N为节点的个数

struct e{

int v;

e* nxt;

}es[N<<1], *fir[N];

struct node{

int ls, rs; //左右儿子的下标，为-1表示空

int l, r; //区间的左右标号

//数据域,根据不同的需要添加，数据的down和update和线段树的无异

int mid() { return (l + r) >> 1; }

}nodes[N<<1];

int n, en;

int que[N], par[N], dep[N], root[N], seg[N], st[N], ed[N], top[N], sons[N], id[N];

//que用于BFS，par记录父节点，dep记录节点的深度。 root[i]为链i的根节点，seg用于在链上建线段树，

//st[i],ed[i]分别为链i的左右端点，top[i]为链i的顶部的节点，sons[i]为节点i的儿子节点

//id[i]是节点i所属的链的标号，

int ln, cnt, tr; //ln是链的个数，cnt为节点的个数,tr是树的根节点

inline void add_e(int u, int v){

es[en].v = v;

es[en].nxt = fir[u];

fir[u] = &es[en++];

}

inline void newNode(int& id, int l, int r){

nodes[cnt].ls = nodes[cnt].rs = -1;

nodes[cnt].l = l;

nodes[cnt].r = r;

id = cnt++;

}

void build(int& id, int l, int r){ //在剖分出来的链上构建线段树

newNode(id, l, r);

if(l >= r){

//seg[l]为落在这个线段树节点上的原树中的节点

return ;

}

int mid = (l+r)>>1;

build(nodes[id].ls, l, mid);

build(nodes[id].rs, mid+1, r);

}

void initTree(){ //初始化剖分树

//确定父亲

int l, r, u, v, i;

e* cur;

l = r = 0;

que[r++] = tr;

par[tr] = -1;

dep[tr] = 0;

while(l != r){

u = que[l++];

int g = 1;

for(cur = fir[u]; cur; cur = cur->nxt){

if((v = cur->v) != par[u]){

que[r++] = v;

par[v] = u;

dep[v] = dep[u]+1;

}

}

}

//计算子树大小

for(i = 1; i <= n; i++){

sons[i] = 1;

id[i] = -1;

}

for(i = r-1; i >= 0; i--){

u = que[i];

if(par[u] >= 0){

sons[par[u]] += sons[u];

}

}

//剖分链

l = r = 0;

que[r++] = tr;

ln = cnt = 0;

while(l != r){

u = que[l++];

st[ln] = dep[u]; //用节点的深度作为线段树中区间的左右标号

top[ln] = u;

while(u >= 0){

id[u] = ln;

ed[ln] = dep[u];

seg[dep[u]] = u;

int best;

for(cur = fir[u], best=-1; cur; cur = cur->nxt){

if(id[v = cur->v] == -1){

if(best == -1 || (best >= 0 && sons[v] > sons[best])){

best = v;

}

}

}

if(best >= 0){

for(cur = fir[u]; cur; cur = cur->nxt){

if(id[v = cur->v] == -1 && best != v){

que[r++] = v;

}

}

}

u = best;

}

root[ln] = -1;

build(root[ln], st[ln], ed[ln]);

ln++;

}

}

void lqry(int& id, int ql, int qr){

if(id == -1) return ;

if(ql <= nodes[id].l && nodes[id].r <= qr){

return ;

}

if(nodes[id].l == nodes[id].r){

return ;

}

int mid = (nodes[id].l+nodes[id].r)>>1;

if(ql <= mid){

lqry(nodes[id].ls, ql, qr);

}

if(qr > mid){

lqry(nodes[id].rs, ql, qr);

}

}

void qry(int u, int v){ //查询u和v之间的最大值

while(id[u] != id[v]){

if(id[u] > id[v]){

swap(u, v);

}

int b = id[v];

lqry(root[b], st[b], dep[v]);

v = par[top[b]];

}

if(dep[u] > dep[v]){

swap(u, v);

}

lqry(root[id[u]], dep[u], dep[v]);

}

int main(){

return 0;

}

</PRE>

&nbsp;