基本定義
樹鏈剖分:
目標: 一顆樹,,將其劃分為若干條鏈,,,每個點屬於且僅屬於一條鏈,,,
劃分的方法很多,,,不過按某種方法劃分卻有一條很好的性質,,,任意一點到根結點的路徑上的鏈的個數不超過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\n", 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\n",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>
