看了這麼久終于看懂學長給的樹上倍增代碼了 下面就來盤點一下那些難以了解的地方 先把學長的部落格也放出來https://blog.csdn.net/qq_41635132
前導知識是RMQ沒有學過的同學先去學一下哦
先說一下樹上倍增的基本原理 友善下面的閱讀
我們先想一下 如果找 節點 8 和節點 5 的最小公共祖先 是不是等于找 4 5的公共祖先 這裡4是8的祖先 且4 和 5在同一層
那麼為什麼放到同一層才行呢 看看我們的題目 樹上倍增 我們待會要開始倍增了 那麼怎麼個倍增方法呢 兩個同一層的節點 如果同時上跳2^n步是不是還在同一層呢？ 答案是肯定的 那麼這有什麼用處呢
我們假設這是 4 和 5的情況 從圖中我們可以看到它們的lca 是 節點A
那隻要我們上跳的時候上跳到a 4 和 5就相遇了對吧。
那麼怎麼上跳呢下面就是倍增
我們每次上跳2^(i–)步 如果上跳之後兩個相遇 就證明我們跳過了對吧
那麼就排除掉 接着下一次的跳躍 如果上跳之後沒有相遇我們就移動 4 和5的位置 從圖中可以看到 最近一次跳躍應該是 2^1的時候 這時候我們再走一步就到了公共祖先 這時候就可以停止了（注意不是上跳到AA點 因為我們不能讓他們再同一點相遇 我們隻需讓他們保持他們兩個是A的兩個子節點就行 最後我們可以傳回 4上面一個節點（也就是A））
那麼為什麼我們不跳到A呢？ 因為如過到兩點相遇就傳回的話我們的判斷語句應該是這樣的
if(4上跳x步數之後==5上跳x步數之後)
return 4 和 5 相遇的地方
看出來了嗎 寫成代碼傳回條件就是4和5相遇就傳回了 那麼我們就不能确定到底傳回的節點是不是最小的公共祖先節點了
下面我們配着題來了解
下面這份代碼是A - How far away ？ HDU - 2586的答案
Problem Description
There are n houses in the village and some bidirectional roads connecting
them. Every day peole always like to ask like this "How far is it if I
want to go from house A to house B"? Usually it hard to answer.
But luckily int this village the answer is always unique, since the roads
are built in the way that there is a unique simple path("simple" means you
can't visit a place twice) between every two houses. Yout task is to
answer all these curious people.
Input
First line is a single integer T(T<=10), indicating the number of test
cases.
For each test case,in the first line there are two numbers
n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of
queries. The following n-1 lines each consisting three numbers i,j,k,
separated bu a single space, meaning that there is a road connecting house
i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n.
Next m lines each has distinct integers i and j, you areato answer the
distancebetween house i and house j.
Output
For each test case,output m lines. Each line represents the answer of the
query.
Output a bland line after each test case.
Sample Input
2
3 2
1 2 10
3 1 15
1 2
2 3
2 2
1 2 100
1 2
2 1
Sample Output
10
25
100
100
完整代碼 完整代碼下面會分解出來分析
#include<cstring>
#include<cstdio>
#include<iostream>
#pragma warning (disable:4996)
using namespace std;
const int maxn = 40010;
struct edge//學長本人喜歡把模闆寫到結構體裡面 就按着這個解釋了
{
int to[maxn << 1], value[maxn << 1];
int head[maxn], Next[maxn << 1];
int cnt;
void init() { memset(head, -1, sizeof head), cnt = 0;}
void add(int f, int t, int v)
{
to[++cnt] = t;
value[cnt] = v;
Next[cnt] = head[f];
head[f] = cnt;
}
}e;
int n, m;
int dep[maxn], dis[maxn], dp[maxn][22];
void dfs(int rt) {
dep[rt] = dep[dp[rt][0]] + 1;
for (int i = 0; dp[rt][i]; i++)
dp[rt][i + 1] = dp[dp[rt][i]][i];
for (int i = e.head[rt]; ~i; i = e.Next[i]) {
if (dep[e.to[i]])continue;
dis[e.to[i]] = dis[rt] + e.value[i];
dp[e.to[i]][0] = rt;
dfs(e.to[i]);
}
}
int lca(int a, int b) {
if (dep[a] < dep[b]) swap(a, b);
for (int i = 20; i >= 0; i--)
if (dep[dp[a][i]] >= dep[b])
a = dp[a][i];
if (a == b) return a;
for (int i = 20; i >= 0; i--)
if (dp[a][i] != dp[b][i])
a = dp[a][i], b = dp[b][i];
return dp[a][0];
}
int main()
{
int t;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
e.init();
for (int i = 0; i <=n; i++)
dep[i] = 0;
int a, b, v;
for (int i = 1; i < n; i++) {
scanf("%d%d%d", &a, &b, &v);
e.add(a, b, v), e.add(b, a, v);
//注意哦 因為是無向圖 是以我們得加兩次
}
dis[1] = 0, dfs(1);//為什麼是1 其他數其實也可以
//但是無論n是多少 1<=n 恒成立 是以選擇1當作根節點
//為什麼1就是根節點了呢 解釋再下面哦
while (m--) {
scanf("%d%d", &a, &b);
printf("%d\n", dis[a] + dis[b] - 2 * dis[lca(a, b)]);
//不再詳細解釋這裡了
}
}
return 0;
}
分解時間
結構體解釋
//下面我們把 to[],value[],head[],Next[]這四個數組放到一起看
to[i],value[i],head[i],Next[i]一起記錄了一組輸入給我們帶來的資訊
struct edge
{
int to[maxn << 1], value[maxn << 1];
int head[maxn], Next[maxn << 1];
int cnt;
void init() { memset(head, -1, sizeof head), cnt = 0;}
void add(int f, int t, int v)
{
to[++cnt] = t; //to數組就是記錄了f 能到達的一個地方
value[cnt] = v;//value記錄了 f 和 t兩個節點之間的距離
Next[cnt] = head[f];
//先看head head[]剛開始都是0
//然後 head[i]記錄的是上一組以和f有關的資料的出現的地方
//比如我第三組資料輸入的是 1 2 3 add(1,2,3)之後Next[3]=0,head[1]=3
//(其實不是三昂是2*(3-1)+1, 因為後面會再add(2,1,3)，這是一個無向圖)
//代表上一次 出現過1這個節點的地方在第三組資料 這樣通過這種關系我們
//可以快速找到 1這個節點能到達的所有節點 dfs的時候會仔細說明
head[f] = cnt;//更新一下head[f]的值 最近一次出現f的地方是
//第cnt組資料;
}
小插曲
int dep[maxn], dis[maxn], dp[maxn][22];
//dep[]用來記錄該節點的深度
// dp[i][j]用來記錄 i節點往上走2^j步之後是哪個節點()
dfs環節到
void dfs(int rt) {
dep[rt] = dep[dp[rt][0]] + 1;//注意以上越是上層的節點depth越小
//rt的深度就等于rt一層節點的深度加一
//注意判斷條件如果已經到了0這個
//節點的話 就不用再往下比對了因為0已經是最原始的節點了（
//實際上沒有把這個節點放到樹裡面這麼說知識為了友善了解）
for (int i = 0; dp[rt][i]; i++)
dp[rt][i + 1] = dp[dp[rt][i]][i];//這裡就是更新一下rt的2^j層之上是哪一個節點
//以rt為爸爸 把它所能到達的所有節點看錯它的子節點
for (int i = e.head[rt]; ~i; i = e.Next[i]) {
if (dep[e.to[i]])continue;
//如果e.to[i]這個節點節點已經通路過了 那就繼續往下查找
dis[e.to[i]] = dis[rt] + e.value[i];//更新一下值
dp[e.to[i]][0] = rt;
//rt是e.to[i]節點的爸爸 e.to[i]往上走2^0步就是它的爸爸
dfs(e.to[i]);//然後對e.to[i]找兒子
}
}
可能存在的疑問 為什麼dfs()之後就能把所有節點涵蓋進去
我們想一下一棵樹
0
1 2
3 4 5 6
是不是轉換成這樣
1
3 4 0
2
5 6
雖然我不想見到這麼醜的樹 但是我們不能剝奪它的樹籍
根據這兩個圖 我們可以得出 dfs(rt) 傳入的這個rt 就被我們人為
改變成根節點了 那麼往下也就能解釋為什麼會找到每一個節點了
靈魂所在 倍增之路開始了
//找a和b的公共爸爸
int lca(int a, int b) {
if (dep[a] < dep[b]) swap(a, b);
//這裡預設把a看作靠下面一層的節點 僅僅是為了友善 把b看成靠下的也行
//這個for循環時找到a的祖先中與b的深度相同的一個
for (int i = 20; i >= 0; i--)
if (dep[dp[a][i]] >= dep[b])//注意判斷條件 >=
a = dp[a][i]; //for搞完之後就是 a就是和b同一級了
//注意我們最終的傳回值僅僅是a（原本） 和 b的公共祖先 這裡a（現）
//已經是a的祖先了（也有可能是本身) 是以不用管a的變化會導緻邏輯錯誤
//為啥一定能傳回的是a的祖先呢 下面再仔細解釋 看懂的同學可以忽略了昂
if (a == b) return a;//不解釋這裡了
//這個for循環就是找公共祖先的時候了
//先看函數傳回值是 dp[a][0] 是以最後dp[a][0]代表的就是他們公共祖先
//又因為是dp[a][0]是以 這時候 a 和 b都是dp[a][0]這個節點的"親兒子"
//見下圖 原諒我是用ppt畫的圖。。。
for (int i = 20; i >= 0; i--)
if (dp[a][i] != dp[b][i])
a = dp[a][i], b = dp[b][i];
return dp[a][0];
}
關于為什麼返最終的a是a(原)的父親 且與b深度一樣的
我們先假設 a與b的深度差是9
那麼我們可以跳 2^3 步 再跳2^0 次方步就可以了對吧
那如何證明别的深度差也可以跳到呢？
答案就是二進制
任何一個深度差都是一個整數 我們把它轉化成一個二進制之後
先瞎寫一個數哈
11010 是不是可以先跳2^4 步 然後2 ^3次方步 然後 2^1 步就行了
a往上走一步就是dp[a][0];
main函數就不再細說了 相信大家也都能看懂了