最近公共祖先算法在管道運輸的應用

黃檢寶，彭詩怡，郭煜銳

（南華大學，衡陽421001）

0 引言

國家發改委在2017 年1 月19 日，引發了《十三五規劃》，我國管道運輸的總里程增量十分巨大[1]，在互聯網大數據時代背景下，如何用智能算法監控管道運輸顯得尤為重要。最近公共祖先算法是圖論的經典算法，它能夠快速地找出樹中兩點的最近公共祖先[2-3]，相對于樸素的暴力搜索算法，其有較低的時間復雜度，本文通過最近公共祖先算法實現了快速監控管道網絡中的最大流量，保障了管道運輸的安全。

1 最近公共祖先算法

1.1 概述

對于有根樹T，結點u 和v 的最近公共祖先為LCA(u,v) ，LCA(u,v) 滿足為u和v的深度最大的父結點。例如，存在樹T0，其點集為V{1,2,3,4,5,6}，邊集為E{(1,2),(1,3),(2,4),(2,5),(5,6)} ，令根結點為1，如圖1 所示，結點4 和結點6 的公共祖先有結點1 和結點2，由于結點2 的深度比結點1 的深度大，所以結點2 是結點4 和結點6 的最近公共祖先。

圖1 示例圖（一）

最近公共祖先問題的算法，主要包括歐拉序結合ST 表法、倍增法[3]、并查集[2-3]結合Tarjan 算法[4]和樹鏈剖分法[2]。其中包括離線算法和在線算法，離線算法需要提前知道所有要求LCA 的點對{(ui),vi,…}，再一次性處理，得到所有的點對的公共祖先；而在線算法可以合理的根據需求，每輸入一對u 和v，即可求出他們的LCA。這四種算法中，除了并查集結合Tarjan 算法為離線算法，其他都是在線算法。歐拉序結合ST 表法的核心思想是首先通過深度優先搜索得到有根樹的歐拉序，然后通過ST 表不斷查詢兩點的LCA；倍增法的核心思想是，將兩點同時往根節點跳躍2 的指數倍，當深度差相等時，即可得到兩點的LCA；并查集結合Tarjan算法的核心思想為，在深度優先搜索返回的過程中，不斷的用并查集合并搜索到的點，LCA 為并查集根節點。樹鏈剖分的核心思想為，將樹劃分為輕重鏈，然后用線段樹或者樹狀數組來維護每一條鏈，LCA 即為數據結構查詢得到的結果。

1.2 歐拉序和ST表

最近公共祖先問題，包括四大算法，有線算法更具有實際應用價值，下面對歐拉序和ST 表法求LCA 進行詳細介紹。

歐拉序是對圖搜索過程中，記錄搜索路徑中遍歷的結點，每次經過的點都需要記錄。與dfs 序不同的是，dfs 序類似于前序遍歷，只是將第一次遍歷的點按順序記錄下來。以圖1 為例，歐拉序為：{1，2，4，2，5，6，5，2，1，3，1}，dfs 序為：{1，2，4，5，6，3}。

ST 表是一種能實現快速查找區間最大值或者最小值的數據結構，它通過二的冪次方來劃分區間，不斷的利用上一個小區間，合并求出當前大區間的最大值或者最小值，而查詢時只需要將查詢的區間劃分為盡可能大的二次冪區間，重疊覆蓋取其最大值或最小值即可得到結果。

將這兩個算法結合，首先遍歷樹得到歐拉序，然后在歐拉序中使用ST 表快速查找LCA，例如，在圖1 中，求結點4 和結點6 的最近公共祖先，在歐拉序中找到結點4 和結點6 第一次出現的位置，即第3 個和第6個，對應的序列為{4，2，5，6}，再利用ST 表查詢第3 個位置和第6 個位置之間的最小值，即LCA 為{4，2，5，6}的最小值，結果是結點2。

2 管道運輸問題

A 國建立了一個龐大的石油管道運輸網絡，如何才能快速的監控管道網絡的流量，來保障石油運輸過程中的安全性呢？A 國有N 個城市，為了節省管道的材料費，A 國只布置了N-1 條石油運輸管道，即剛好能保證兩兩城市之間能互通，沒有城市是孤立狀態。現在A 國管道運輸管理者經常需要增加某兩個城市之間的石油流量，假設每增加1 單位流量，兩城市之間的管道也會增加1 單位壓力，經過多次操作后，A 國整個管道網絡最大的壓力是多少？

算法的輸入格式為：第一行輸入整型N，代表A 國城市的數量，之后輸入N-1 行整型ai和bi之，代表城市ai和城市bi之間有一條管道連通，再輸入整型k 代表需要對管道網絡進行k 次操作，輸入k 行aj，bj和cj，分別代表城市aj和城市bj經過的管道流量增加cj單位。（2≤N≤50000，1≤k≤100000）

算法的輸出格式為：輸出一行整型數據，即整個管道網絡的最大壓力。

3 算法分析與設計

3.1 問題簡化

A 國的管道運輸網絡看做一個無向圖，有N 個點、N-1 條邊，兩兩點之間剛好相互可達，那么這個無向圖不存在環，因此它也是無根樹。對無根樹T1中某些路徑經過k 次增流，每次增流相當于增加邊權，最終需要求k 次增流后的最大邊的權值是多少。下面，通過LCA 和樹上標記算法來解決這個問題，并分析為什么樹上差分不可以有效地解決此問題。

3.2 數列區間操作

（1）數列差分

數列區間操作常用的方法為數列差分[3]，從數列差分的角度進行推廣，對樹鏈操作，因此想到樹上差分，下面先介紹數列差分。數列差分可以做到批量操作數列區間加減法或者乘除法，適用于需要多次操作區間的情況。與枚舉算法對比，枚舉算法每次操作需要遍歷區間，時間復雜度為O（n2)，而數列差分只需要將需要操作的端點標記即可，最后遍歷一遍數列即可得到最終的結果，時間復雜度為O（n）。

例如，存在數列{1，5，6，2，5，5}，分別對區間[0，4]、[1，5]的每個數加1，首先計算出差分數組d={1，4，1，-4，3，0，0}，然后處理端點，對于區間[0，4]，將d[0]++，d[4+1]--，對于區間[1，5]，d[1]++，d[5+1]--，最終d={2，5，1，-4，3，-1，-1}，之后求d 數列的前綴和，即為最終答案：d={2，7，8，4，7，6}（答案只取前六個數）。

（2）數列標記

同樣是對數列區間操作，不使用到差分，只對區間端點標記，也可以在O（n）時間復雜度下解決問題。同樣在上一個例子的基礎上，設標記數組為flag={0，0，0，0，0，0，0}，若[0，4]、[1，5]每個數都加1，則flag[0]++、flag[4+1]--、flag[1]++、flag[5+1]--，flag={1，1，0，0，0，-1，-1}，flag 前綴和為s={1，2，2，2，2，1，0}，這個數列就是原數列每個數的增量，因此，最終結果為{1+1，5+2，6+2，2+2，5+2，5+1}，即{2，7，8，4，7，6}。

3.3 LCA求解管道運輸問題

（1）LCA 與樹上差分

類比數列差分，結合LCA 做樹上差分，能做到多次操作某一條鏈的權值。假設根節點為結點1，dis[i]代表結點i 前向邊的差分流量，從結點1 開始遍歷，首先求出初始的dis 數列，之后，若對結點aj到結點bj中每一條邊加cj，因為涉及到操作LCA（aj，bj）的子結點，且又無法直接判斷LCA（aj，bj）的子結點，是否在結點aj到結點bj的路徑上，因此需要對結點aj到結點bj的路徑搜索。

圖2 示例圖（二）

如圖2 所示，對結點7 和結點8 的路徑權值都增加1，LCA(7,8)為結點2，因為結點4 和結點5 在路徑之上，并且為結點2 的子結點，因此dis[4]++，dis[5]++，對結點7 和結點8 的子結點操作，dis[10]--，dis[11]--，最后從結點1 開始求一遍前綴和即可。（這里在確定結點4 和結點5 時，則需要對結點7 到結點8 的路徑搜索。）

時間復雜度分析：k 次詢問，每次都需要對路徑進行搜索，為O（n），所以總的復雜度為O（kn），與樸素的暴力搜索算法時間復雜度一致，因為用到了LCA 和其他的處理，因此時間復雜度常數會更大，總的來說還不如暴力搜索法。

（1）LCA 與樹上標記

將根結點作為參考點，此時將dis[i]定義為結點i到根結點路徑上邊的增量，pre[i]定義為結點i 的前向邊權，若對結點aj到結點bj中每一條邊加cj，則dis[aj]+=cj，dis[bj]+=cj，dis[LCA（aj，bj）]-=cj，最后后序遍歷樹T1，原始的邊的權值加上dis 的增量和，即為操作k 次后的邊權結果，并求出邊權的最大值即為問題結果。

圖3 示例圖（三）

如圖3 所示，對結點7 和結點8 的路徑權值都增加1，dis[7]++，dis[8]++，dis[2]-=2，計算dis 從葉子結點到根節點的累積增量，從結點7 至結點1，從結點8 至結點1，dis[7]=1，dis[4]=1，dis[8]=1，dis[5]=1，dis[2]=dis[4]+dis[5]+dis[2]=0，最終pre[i]+=dis[i]為最終結果。

算法復雜度分析：LCA 使用歐拉序結合ST 表的方法，ST 表預處理的時間復雜度為O（nlog2n），查找的復雜度為O（1），樹鏈操作都轉化為標記，最后只需要遍歷求出累積值即可，時間復雜度為O（n），所以整個算法時間復雜度為O（nlog2n）。

4 結語

本文分析了歐拉序、ST 表、數列區間問題和樹上路徑問題，結合歐拉序和ST 表能求出樹上兩結點的最近公共祖先，再以根節點為參考進行樹上標記，能在O（nlog2n）的時間復雜度下，求解出了管道網絡的最大壓力，而暴力搜索算法和樹上差分算法的復雜度為O（kn），由此可知在需要查詢的次數k 較多時，本文提出的最近公共祖先和樹上標記算法，能大大節省計算資源，在管道運輸監控上具有較大價值。