淺談樹鏈剖分（C++、算法、樹結構），淺談

淺談樹鏈剖分（C++、算法、樹結構），淺談

關於數鏈剖分我在網上看到的有幾個比較好的講解，本篇主要是對AC代碼的注釋（感謝各位witer的提供）

這是講解

http://www.cnblogs.com/kuangbin/archive/2013/08/15/3259083.html

另一個是百度文庫

http://wenku.baidu.com/link?url=DY8CAbwdjitIiv8XQsHmVPi--dQAqw5z6dc_6N1Plh4u5Nfc1aCADQm4oAvt4Sqe1mXSixezzK4lRxofQKMX9cNzJwYwQhpGJZuMSTI3Ktq

這是AC代碼（以bzoj1036為例題）

http://www.cnblogs.com/kuangbin/archive/2013/08/15/3259083.html

但是我相信很多人有和我一樣的經歷，就是看各種大神的代碼的時候只是膜拜他們的長度和復雜，但是大神們卻並不對代碼進行講解，導致我們和多人看不懂。下來還得自己理解。

這樣會花費很長的時間。。。。TAT！

下面是我對AC代碼的注釋，原文並沒有那麼多。其中沒有關於線段樹的知識，只是對剖分時進行了解釋。對於不了解線段樹的讀者請自行百度。。。。。

希望能對讀者有較大的幫助。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<string>
using namespace std;
const int MAXN = 30010;
struct Edge//E[i].to為邊E[i]指向的點.
{// E[i].next為邊E的上一條邊（即E與E的上一條邊由同一節點發出）.
    int to,next;
}edge[MAXN*2];
int head[MAXN],tot;//head[j]為節點j的最後一條發出邊.
int top[MAXN]; //top[v] 表示v所在的重鏈的頂端節點
int fa[MAXN]; //父親節點
int deep[MAXN];//深樹的度
int num[MAXN]; //num[v]表示以v為根的子樹的節點數
int p[MAXN]; //p[v]表示v在線段樹中的位置
int fp[MAXN];//和p數組相反
int son[MAXN];//重兒子
int pos;
void init()
{
    tot=0;pos=0;
    memset(head,0,sizeof(head));
    memset(son,-1,sizeof(son));
}
void addedge(int u,int v)
{
    edge[++tot].to=v;edge[tot].next=head[u];head[u]=tot;
}
void dfs1(int u,int pre,int d) //第一遍dfs求出fa,deep,num,son
{
    deep[u]=d;//u 深搜到的點 pre u的前驅 d 深度 
    fa[u]=pre;//完成父親數組 
    num[u]=1;//u 包含的點數 
    for(int i=head[u];i;i=edge[i].next){
      int v=edge[i].to;//邊i的指向點 
      if(v!=pre){//判斷是否是i的父親，若是跳出不是繼續深搜
        dfs1(v,u,d+1);//v 深搜到的點 u v的父親（前驅） 深度+1 
        num[u]+=num[v];//父親包含的點數=兒子包含的點數+1 
        if(son[u]==-1||num[v]>num[son[u]])//son==-1時，即沒有標記重兒子，直接標記 
          son[u]=v;// num[v]>num[son[u]]如果v包含的節點數大於其父親的重兒子的節點數，v變為 
      }//                                                              其父親的重兒子 
    }
}
void getpos(int u,int sp)//將重兒子連成重鏈 
{
    top[u]=sp;//sp為傳遞變量，即若sp不變，DFS過程中的重兒子均屬於以sp為根的重鏈 
    p[u]=pos++;//將重鏈的節點放在數組p中，來構建線段樹 
    fp[p[u]]=u;//反之 
    if(son[u]==-1) return;//若son為-1，則該點為葉子節點，返回 
    getpos(son[u],sp);//DFS對u的重兒子，將其加入重鏈中，sp不變 
    for(int i=head[u];i;i=edge[i].next){//邊的循環(將一條重鏈添加完後再對輕邊進行添加) 
      int v=edge[i].to;//v是邊i的指向點 
      if(v!=son[u]&&v!=fa[u]) getpos(v,v);//(v!=fa[u])處理v是u的父親的情況 
    }//若v是u的兒子但不是重兒子(即其屬於輕邊)，以自己為根(修改sp)繼續DFS形成新的重鏈  
}
struct Node//線段樹的點 
{
    int l,r;
    int sum;
    int Max;
}segTree[MAXN*3];
void push_up(int i)
{
    segTree[i].sum=segTree[i<<1].sum+segTree[(i<<1)|1].sum;
    segTree[i].Max=max(segTree[i<<1].Max,segTree[(i<<1)|1].Max);
} 
int s[MAXN];
void build(int i,int l,int r)//建線段樹(不懂的看線段樹的講解)
{
    segTree[i].l=l;
    segTree[i].r=r;
    if(l==r){
      segTree[i].sum=segTree[i].Max=s[fp[l]];
      return;
    }
    int mid=(l+r)/2;
    build(i<<1,l,mid);
    build((i<<1)|1,mid+1,r);
    push_up(i);//用來儲存樹上的和、最大值 
}
void update(int i,int k,int val)//更新線段樹的第k個值為val
{
    if(segTree[i].l==k&&segTree[i].r==k){
      segTree[i].sum=segTree[i].Max=val;
      return;
    }
    int mid=(segTree[i].l+segTree[i].r)/2;
    if(k<=mid)update(i<<1,k,val);
    else update((i<<1)|1,k,val);
    push_up(i);
}
int queryMax(int i,int l,int r)//查詢線段樹[l,r]區間的最大值
{
    if(segTree[i].l==l&&segTree[i].r==r){
      return segTree[i].Max;
    }
    int mid=(segTree[i].l+segTree[i].r)/2;
    if(r<=mid) return queryMax(i<<1,l,r);
    else if(l > mid)return queryMax((i<<1)|1,l,r);
    else return max(queryMax(i<<1,l,mid),queryMax((i<<1)|1,mid+1,r));
}
int querySum(int i,int l,int r) //查詢線段樹[l,r]區間的和
{
    if(segTree[i].l==l&&segTree[i].r==r)
      return segTree[i].sum;
    int mid=(segTree[i].l+segTree[i].r)/2;
    if(r<=mid)return querySum(i<<1,l,r);
      else if(l>mid)return querySum((i<<1)|1,l,r);
        else return querySum(i<<1,l,mid)+querySum((i<<1)|1,mid+1,r);
}
int findMax(int u,int v)//查詢u->v路徑上節點的最大權值
{
    int f1=top[u],f2=top[v];
    int tmp=-1000000000;
    while(f1!=f2){
      if(deep[f1]<deep[f2]){
        swap(f1,f2);
        swap(u,v);
      }
      tmp=max(tmp,queryMax(1,p[f1],p[u]));
      u=fa[f1];
      f1=top[u];
    }
    if(deep[u]>deep[v]) swap(u,v);
    return max(tmp,queryMax(1,p[u],p[v]));
}
int findSum(int u,int v) //查詢u->v路徑上節點的權值的和
{
    int f1=top[u],f2=top[v];//記錄所屬鏈的根節點 
    int tmp=0;
    while(f1!=f2){
      if(deep[f1]<deep[f2]){//同時向上跳 
        swap(f1,f2);
        swap(u,v);
      }
      tmp+=querySum(1,p[f1],p[u]);
      u=fa[f1];
      f1=top[u];
    }
    if(deep[u]>deep[v]) swap(u,v);
    return tmp+querySum(1,p[u],p[v]);
}
int main() 
{
//    freopen("in.in","r",stdin);
//    freopen("out.out","w",stdout);
    int n;
    int q;
    char op[20];
    int u,v;
    while(scanf("%d",&n)==1){
      init();
      for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        addedge(u,v);
        addedge(v,u);
      }
      for(int i=1;i<=n;i++)
        scanf("%d",&s[i]);
      dfs1(1,0,0);
      getpos(1,1);
      build(1,0,pos-1);
      scanf("%d",&q);
      while(q--){
        scanf("%s%d%d",op,&u,&v);
        if(op[0]=='C')  update(1,p[u],v);//修改單點的值
         else if(strcmp(op,"QMAX") == 0)
            printf("%d\n",findMax(u,v));//查詢u->v路徑上點權的最大值
         else printf("%d\n",findSum(u,v));//查詢路徑上點權的和
      }
    }
    return 0;
}

程序員不是打字員而是作家！