樹上倍增一些理解和寫法

樹上倍增可以比較容易求得i節點的第k個父親，我們定義一個二維數組fa[i][j]代表節點i的第2^j個父親，關于有什么用我們等會再說，現在先學會怎么去求這個fa數組

我們可以通過從根節點開始一遍dfs求得所有fa數組，首先我們發現fa數組有這樣一個特性，fa[i][j] = fa[ fa[i][j-1] ][j-1]，什么意思呢，就是說節點i的第2^j個父親就是i的第2^(j-1)個父親的第2^(j-1)個父親，這看起來似乎是一句顯然成立的廢話，但我們可以通過這個特性以O(nlogn)的復雜度內求fa數組。

我們知道dfs是從根開始，一步一步往下走的，這就說明除了根節點，每個節點當它被dfs到的時候，它的所有父親肯定都已經被dfs過了，這樣通過剛才的關系，就可以由i的第2^(j-1)個父親求fa[i][j]了，我們需要處理的只是i的第2^j個父親有可能不存在罷了。我們初始化fa數組為0，然后從根開始dfs。若有n個節點，則顯然一個節點最多只可能往前找2^log(n)個父親

void dfs(int x)  
{  for(int i=1;i<=logn;i++)  //logn代表log(n)if(fa[x][i-1])   //在dfs(x)之前，x的父親們的fa數組都已經計算過了fa[x][i]=fa[fa[x][i-1]][i-1];  else break;    //x的第2^j個父親可能不存在for(/*每一個與x相連的節點i*/)  if(i!=fa[x][0])     //如果i是x的兒子
        {  fa[i][0]=x;       //記錄兒子的第一個父親是x  dep[i]=dep[x]+1;      //深度  
            dfs(i);  }  
}  

?

求出fa數組后有什么用呢？其實我們可以輕易的在O(logk)內求出i的第k個父親，根據數組定義看起來我們只能求i的第2，4，8...2^j次方個父親，實際上我們可以求出i的第任意個父親

我們有這樣一個事實，任何一個數，都可以寫成多個2的x次方的和，實際上這就是2進制轉10進制的過程，比如：10的二進制表示為1010，它的左數第2位和第4位上是1，所以2^(2-1)+2^(4-1) = 2^1 + 2^3 = 10。這個思想很有用，需要記住

所以對于任意一個數k，只要我們把它寫成若干個2的次方形式的數的和，就可以利用fa數組了。

另外我們代碼中還有個技巧，(1<<i)&k表示k的二進制表示中，左數第(i-1)位上是否為1?

經過上面知識我們可以寫出求i的第k個父親的代碼

int father(int i,int k)  
{  for(int x=0;x<=int(log2(k));x++)  if((1<<x)&k)    i=fa[i][x];     return i;  
}  

?