Codeforces 161D - Distance in Tree (點分治講解)

題目大意：

給你一棵樹，保證他們不會形成迴路。詢問這棵樹中有多少 x 的距離。
以下用到的都是使用Dispwnl 博客的點分治講解的圖片，如果 Dispwnl 大大不允許我使用我將會自行刪除，向 Dispwnl 道歉 QQ，也很謝謝他寫的詳細點分治教學讓我對點分治有了解
此篇程式碼大多從 Distance in Tree （CodeForces - 161D，点分治） 學習而來，謝謝作者釋放自己的程式碼，讓我可以完整學習到點分治。

分析

這要使用一種我從來沒有學過的演算法「點分治」，我們先來說說看點分治通常用於甚麼題目。

他專門來解決給定一棵樹和一個整數 k，求此樹上兩點路徑等於小於 k 的有多少？
由於此題是點分治的模板題，只要能夠了解點分治就能解決此問題。
這題為教學題，我們將問題簡單化，只詢問「樹上兩點路徑等於 = k」

點分治介紹

點分治的精隨: 就是不斷把一顆樹拆成子樹來處理，並考慮路徑合併
分治點的選擇: 樹的重心

QUESTION 1: 分治點是甚麼?

分治點就是可以把一顆樹拆成兩棵樹的點。

QUESTION 2: 樹的重心是甚麼?

樹重心的所有子樹大小不超過整個樹大小的一半。

QEUSTION 3: 此演算法的複雜度呢?

\(O(\log n)\)

名詞解釋: 公式

樹的重心到左子樹中的路徑 + 樹的重心到右子樹的路徑 = k

點分治原理操作

如圖，我們先找出樹的重心，在將從樹的重心到左子樹中的路徑 + 樹的重心到右子樹的路徑加起來如果等於 k 我們就加一條路徑，再透過分治的方式，再從子樹的重心在重複一樣動作。可以寫出很玄的遞迴

選樹的重心

樹的重心不可以亂選，如果沒有選好是很浪費效率的，如上圖。

QUESTION : 你想想看如果選到 y 會多浪費時間www。

當讀者學會以後，可以自行回答此問題，也順便增加自己對點分治的能力 XD。

開玩笑的，這篇是要讓讀者能了解點分治的，選 y 的話找路徑需要遞迴 4 次，但選 x 只需要遞迴 2 次，可以得知要找的點要盡量讓遞迴的次數最少為最優，樹的重心是最好的。

建構樹

建構點分治的樹比較抽象，因此拉出來獨立討論：

struct node{ 
    int v , nx ;
     //v = x 可以到此點，路徑為一 , nx 為 x 可以到此點的另外一個 Edge index，一樣是路徑為一 
}Edge[MAXN*2]; 
// 由於無向邊，但此結構是有向所以必須 *2， u -> v , v <- u 各一條。

void init(int n ){
    Max[0] = n ; 
    // Max 是此點最大子樹中的點加起來，0 我們不採用於是就將它設為題目初始長度
    ans = cnt = 0 ;
    for(int i = 0 ; i <= n ; i++){
        head[i] = -1 ; 
        //head 為 i 可以到某個點，路徑為一的 Edge index 
        // head = -1 是因為下面的遞迴停止關鍵為 ~i ， ~(-1) = 0  
        vis[i] = 0 ;
    }
}

尋找樹的重心

透過 DFS + BFS，DFS 來尋找路徑長，BFS 來檢索子樹即可寫出這份遞迴來得知樹的重心：
我相信各位應該看不太懂這程式碼在寫甚麼於是我逐行增加註解。寫得不好，大神請無視

也提供看我之前用紙筆實作的筆記來方便讀者學習，如果還是看不太懂註解那就看看我的實作筆記希望能看懂QQ
寫作筆記 1 get_root (note 1)

//rt = root 
void get_rt(int u , int fa ){
    sz[u] = 1 ; Max[u] = 0 ; 
    //sz 是此點子樹的大小 // Max 是此點最大子樹中的點加起來
    for(int i = head[u] ; ~i ; i=Edge[i].nx){ 
        // 枚舉次點進行的兒子 = 進行長度為一的 BFS(玄學版)
        // 由於 i = Edge[i].nx 於是可以直接找到下一個 i to v 路徑為一的節點
        int v = Edge[i].v ; 
        if(vis[v] || v == fa )  continue ; 
        // vis 表示此點用過了，在第一次找重心時無用。之後會用到。
        get_rt(v,u); // 向下延伸
        Max[u] = max(Max[u] , sz[v]); 
        // 判斷這顆子樹有沒有比此點最大的子樹還要大
        sz[u] += sz[v] ; //更新 sz
    }
    Max[u] = max(Max[u] , n - sz[u]); 
    //用此點將樹分割，分割的兩部分是從此點展開的子樹與另外一個從父節點延伸的子樹 (n - sz[u])
    if(Max[rt] > Max[u]) 
    // 如果現在的最大子樹比較小那就採用現在的點
        rt =  u ;
}

```  

## 尋找從此點到所有子樹中所有點的距離
這遞迴將我們從 u 點到所有點的距離都會求出來。
一樣會每行進行註解，但前面有講到則不再贅述。

```cpp
void get_dis(int u , int fa , int d){ // fa = father , d = distance
    for(int i = head[u] ; ~i ; i= Edge[i].nx){
        int v = Edge[i].v ;
        if(vis[v] || v == fa ) continue ; 
        //如果 v == fa ，代表這點已經沒辦法再向下延伸
        // vis 如果此點有被用到就返回
        dis[++cnt] = d + 1 ; 
        // 由於這裡我們並不在意是哪個點到哪個點的路徑長，我們只在意此路徑長多少，於是我們就用 ++cnt，循序填滿。
        get_dis(v,u,dis[cnt]);
    }
}

求通過此點的子樹們相加起來的路徑長來求答案

透過樹的重心將一顆完整的樹在分割成子樹，詢問如果從 子樹 A 到樹重心 + 子樹 B 到樹重心 = k 的有多少。

int get_ans(int u , int d ){
    dis[cnt=1] = d ;
    get_dis(u,0,d) ;
    sort(dis+1 , dis+cnt+1) ; 
    // 由於 dis 裡面每一個都是從任意一個點到樹重心，透過公式(子樹 A 到樹重心 + 子樹 B 到樹重心 = k)，
    // 我們並不需要在意哪個點只需要在意距離長
    int l = 1 , ans = 0 ;

    while(l < cnt && dis[l] + dis[cnt] < k ) l++ ; 
    // 這時候的 cnt 因為 get_dis 不斷增加數量於是當前的 cnt 也會等於 dis 的右邊界。
    // 我們假設我們先使用 dis[l] 也就是最小路徑去跟其他條進行配合看是否能夠等於 k
    //如果 dis[l] + dis[cnt] 都沒有大於 k 就代表，怎樣都不會大於 k，於是將 l 範圍縮小增進，優化效率。

    while(l < cnt && dis[l] <= k - dis[l]){ 
        ans += upper_bound(dis + l + 1 , dis + cnt + 1 , k - dis[l]) -  \ 
                lower_bound(dis+l+1 , dis+cnt+1 , k-dis[l]);
        // 因為我們的 dis 右邊界是一，所以所有 dis +1
        // k - dis[l]，可以找出我們 k = dis[l] + x， x 為任意變數能夠滿足前述公式即可。
        l++ ; // 再換新的 dis[l] 來進行配合
    }
    return ans ;
}

扣掉重複算到的路徑，用 DFS 實現

我們從 A 到 root + B 到 root，路徑為 4，但這樣是不正確的，因為 A , B 都在同一個子樹並沒有符合我們一直強調的公式。於是我們需要做一個 BFS + DFS，再將重心的點分割成子樹再進行 get_dis and get_ans 的動作，就可以避免掉圖片中的問題。

如果還有點疑問，看程式碼八，也許程式碼的註解可以幫助到你。

void dfs(int u ){
    vis[u] = 1 ; // 被用過的點，也是我們用來分割子樹的標準
    //cout << rt << ' ' << u << '\n' ;
    ans += get_ans(u , 0); // 得到公式中的 k，裡面會有不合法狀態，圖片中的問題。 
    for(int i = head[u] ; ~i ; i = Edge[i].nx){
        int v = Edge[i].v ;
        if(vis[v]) continue ;
        ans -= get_ans(v , 1) ; // 移除掉不合法的狀態 
        // QUESTION: 為甚麼這行可以移除掉不合法狀態呢?
        /* 我們看看上面的圖，他們是不是共用了至少同一條路徑？，如果共用很多條也沒關係
        ，之後的 DFS 就會注意到他們並解決這些問題。
        於是我們就可以用 get_ans(v,1) 用子樹的下一個點來進行一次 DFS，
        我們在假設 x -> v 這條路徑會被共用，所以先直接設定成 1，
        這樣只要是不合法的答案在這邊都會被發現，就可以直接減掉就剩下合法答案了！

        讀者如果還是不懂，可以嘗試將途中橘色的線(共用路徑)進行 +1 後再用 son 去算 dis_ans(son,1)
         去算 a, b 看 k = 4 時是不是也會有一條 XD。
        */
        n = sz[v] , rt = 0 , get_rt(v,u); //由於子樹被切割，所以 n 的 size 也必須減少成子樹的大小。
        //由於樹被切割，所以必須重新尋找被切割樹後重心。
        dfs(rt); //再將樹進行切割，來配合公式。
    }
}

也提供看我之前用紙筆實作的筆記來方便讀者學習，如果還是看不太懂註解那就看看我的實作筆記希望能看懂QQ
寫作筆記 2 dfs and get_ans and get_dis (note 2)

小貼心:由於我認為會有讀者對於在程式碼裡面放 QUESTION，閱讀不太方便，所以拉出來再寫一遍

QUESTION: 為甚麼這行可以移除掉不合法狀態呢?

SOLUTION :

我們看看上面的圖，他們是不是共用了至少同一條路徑？，如果共用很多條也沒關係，之後的 DFS 就會注意到他們並解決這些問題。
於是我們就可以用 get_ans(v,1) 用子樹的下一個點來進行一次 DFS，我們在假設 x -> v 這條路徑會被共用，所以先直接設定成 1，這樣只要是不合法的答案在這邊都會被發現，就可以直接減掉就剩下合法答案了！

讀者如果還是不懂，可以嘗試將途中橘色的線(共用路徑)進行 +1 後再用 son 去算 dis_ans(son,1) 去算 a, b 看 k = 4 時是不是也會有一條 XD。

參考連結

Dispwnl 的博客-点分治略解
点分治学习笔记
Distance in Tree （CodeForces - 161D，点分治）

心得

老實講，我其實學習起來是很吃力的。可能是因為我的基礎知識還不足以讓我可以閱讀我參考連結所放的文章，畢竟我的程式能力跟各位大神比還只是一個還在吃奶的小孩，很多大神可能都懂的東西，我都不懂，所以理解起來也會特別吃力，總是要先看一遍講解在自己用紙筆實作一遍程式碼才可以懂大神們的思維，但我真的很感謝大神，如果沒有他們，我連學習的機會都沒有。

雖然說用紙筆實作一遍程式碼很浪費時間，大概花了 5 小時理解吧，但它確實是最容易理解的，我只實作一遍我就能理解大神們的操作，如再 DFS 的遞迴中加入 BFS，使用那種 for 寫法www。

雖然每次在學習演算法總是會讓我覺得難過，因為是自學很容易遇到學習障礙，但我認為這是我應該要學會的基礎。我並不是幸運的孩子，我勢必要先做出一些成果，讓資源跟大神可以關注到我，在提拔我或幫助我成長。在還沒有大神們關注到我之前，我會默默耕耘，繼續努力的！

為了讓讀者與未來的我看到之前的我學習是怎麼學習的，我就在這邊放入我為了學習這份演算法而在紙上實作的紀錄吧！

寫作筆記 1 get_root (note 1)

寫作筆記 2 dfs and get_ans and get_dis (note 2)

此題目程式碼

還真虧讀者可以讀到這邊，我也花了三個小時撰寫文章，如果是已經懂點分治的朋友們應該會覺得很煩吧！雖然我覺得懂點分治的大神並不會對這題感到困難www，就不會來看我的文章了 XD

對，如題目大意所說，這題就只是個模板題，於是剩下的就是一些標頭檔跟題目給的資料範圍限制了 XD。

#include<iostream>
#include<bits/stdc++.h>
#define LOCAL
#define MAXN 50005
using namespace std;

int n , k , a , b ;
int ans , cnt ;
int Max[MAXN] , sz[MAXN] , rt ;
int head[MAXN], dis[MAXN];
bool vis[MAXN] ;
struct node{
    int v , nx ;
}Edge[MAXN*2];

void init(int n ){
    Max[0] = n ;
    ans = cnt = 0 ;
    for(int i = 0 ; i <= n ; i++){
        head[i] = -1 ;
        vis[i] = 0 ;
    }
}

void add(int u , int v){
    Edge[cnt].v = v ;
    Edge[cnt].nx = head[u] ;
    head[u] = cnt++ ;
}

void get_rt(int u , int fa ){
    sz[u] = 1 ; Max[u] = 0 ;
    for(int i = head[u] ; ~i ; i=Edge[i].nx){
        int v = Edge[i].v ;
        if(vis[v] || v == fa )  continue ;
        get_rt(v,u);
        sz[u] += sz[v] ;
        Max[u] = max(Max[u] , sz[v]);
    }
    Max[u] = max(Max[u] , n - sz[u]);
    if(Max[rt] > Max[u])
        rt =  u ;
}

void get_dis(int u , int fa , int d){
    for(int i = head[u] ; ~i ; i= Edge[i].nx){
        int v = Edge[i].v ;
        if(vis[v] || v == fa ) continue ;
        dis[++cnt] = d + 1 ;
        get_dis(v,u,dis[cnt]);
    }
}


int get_ans(int u , int d ){
    dis[cnt=1] = d ;
    get_dis(u,0,d) ;
    sort(dis+1 , dis+cnt+1) ;
    int l = 1 , ans = 0 ;

    while(l < cnt && dis[l] + dis[cnt] < k ) l++ ;
    while(l < cnt && dis[l] <= k - dis[l]){
        ans += upper_bound(dis + l + 1 , dis + cnt + 1 , k - dis[l]) - lower_bound(dis+l+1 , dis+cnt+1 , k-dis[l]);
        l++ ;
    }
    return ans ;
}

void dfs(int u ){
    vis[u] = 1 ;
    //cout << rt << ' ' << u << '\n' ;
    ans += get_ans(u , 0);
    for(int i = head[u] ; ~i ; i = Edge[i].nx){
        int v = Edge[i].v ;
        if(vis[v]) continue ;
        ans -= get_ans(v , 1) ;
        n = sz[v] , rt = 0  , get_rt(v,u);
        dfs(rt);
    }
}

int main(){
//#ifdef LOCAL
//    freopen("in1.txt" , "r" , stdin);
//#endif // LOCAL

    cin >> n >> k ;
    init(n);
    for(int i =1; i < n ; i++){
        cin >> a >> b ;
        add(a,b);
        add(b,a);
    }
    rt = 0 ; get_rt(1,0);
    dfs(rt);
    cout << ans << '\n' ;

}