下午樹圖基本應(yīng)用基礎(chǔ)

樹和圖的基礎(chǔ)應(yīng)用JiangsuHuaiyinVocationalandTechnicalSchoolzcysky什么是樹和圖？一種數(shù)據(jù)的組織處理方式線性表->樹->圖是從特殊到一般的關(guān)系。為啥要學(xué)這些東西呢？因為NOIP要考也是為學(xué)習(xí)高級數(shù)據(jù)結(jié)構(gòu)等打下基礎(chǔ)。我們會講什么？樹：（我們假設(shè)大家都會存儲以及dfs遍歷）樹的一些概念：重心，直徑。樹上節(jié)點的最近公共祖先（LCA）。最近公共祖先的應(yīng)用。我們會講什么？圖：（假設(shè)各位同學(xué)已經(jīng)掌握圖的存儲，遍歷）圖的最短路徑算法圖的最短路徑算法活用圖的最小生成樹算法拓?fù)渑判驑涞囊恍┗A(chǔ)性質(zhì)一對多的關(guān)系，一個父親有多個孩子。層次性，遞歸定義。邊數(shù)=點數(shù)-1樹上兩點之間路徑唯一，不存在環(huán)。樹的一些奇奇怪怪的東西樹的重心。什么是樹的重心呢？就是如果選擇一個點作為這棵樹的根節(jié)點，可以使得剩下的部分相對較小。（也就是大小接近）可以用來干嘛呢？比如樹的分治算法。如何求樹的重心呢？重心的性質(zhì)：性質(zhì)1：樹中所有點到某個點的距離和中，到重心的距離和是最小的，如果有兩個重心，到他們的距離和一樣。性質(zhì)2：把兩棵樹通過某一點相連得到一顆新的樹，新的樹的重心必然在連接原來兩棵樹重心的路徑上。性質(zhì)3：一棵樹添加或者刪除一個節(jié)點，樹的重心最多只移動一條邊的位置。解法：運用重心的性質(zhì)那么找到一顆樹的重心有以下算法：（1）dfs一次，算出以每個點為根的子樹大小。（2）記錄以每個結(jié)點為根的最大子樹的大小。（3）判斷：如果以當(dāng)前結(jié)點為根的最大子樹大小比當(dāng)前根更優(yōu)，更新當(dāng)前根。一些樹的重心的例題POJ1655題意:給定一棵樹,求樹的重心的編號以及重心刪除后得到的最大子樹的節(jié)點個數(shù)size,如果size相同就選取編號最小的.樹的重心裸題。樹的直徑樹的直徑是什么呢？就是樹上最長的一條樹鏈。直徑我們怎么求呢？方法1：動態(tài)規(guī)劃我們直接求這個最長鏈似乎并不是很簡單，但是如果我們枚舉樹上一個點，可以發(fā)現(xiàn)經(jīng)過這個點的最長鏈一定是由從這個節(jié)點出發(fā)向子樹的最長鏈+不在同一個子樹的次長鏈組成。于是這個問題就可以隨便dp解決了。方法二：dfs這里不給出嚴(yán)格證明，只是簡單的理解一下：直徑是一棵樹上最長的一條樹鏈。那么我們先求出到一個點最遠(yuǎn)的點。很顯然，這條路徑大概是這樣：跑到直徑，然后沿著直徑到最后一個端點。這樣我們就找到了直徑的一個端點。在進(jìn)行一遍同樣的dfs，求出另一個端點，就知道了答案。兩個算法的復(fù)雜度均為O(n)一個簡單的題現(xiàn)給出一個樹，以及每條邊的權(quán)值，現(xiàn)在需要重新構(gòu)建一個樹，每條邊的權(quán)值為原樹上兩點之間的距離。問權(quán)值之和最大為多少。先找出直徑，然后再搜索出每個點分別到直徑的兩個端點的距離，求和并加上直徑的長度即答案。最近公共祖先(LCA)什么是最近公共祖先呢？其實是一個很好懂的定義，就是從兩個點一直向上走，第一個相遇的節(jié)點就是最近公共祖先。這個東西的用途很多，比如如下的這個例子。從一個小問題說起

給定一棵樹，每次詢問樹上兩個點之間的最短距離。直接從一個點開始bfs，直到找到目標(biāo)點？或者使用例如spfa之類的最短路徑算法？上述做法都是naive的。因為樹不是一般的圖，樹有他自己的性質(zhì)，強行忽略這些性質(zhì)做題第一會帶來很大的復(fù)雜度，第二也喪失了這種結(jié)構(gòu)的優(yōu)美性。分析性質(zhì)前面講過，樹的邊數(shù)=點數(shù)-1也就是說，樹的點對之間路徑是唯一的，只要不無聊去走重復(fù)的點，走到的路徑肯定是唯一而且最短的（也就是所謂的簡單路徑）那么畫一個圖，我們發(fā)現(xiàn)路徑的情況其實只有兩種。記錄下一個節(jié)點相對于根節(jié)點的深度d，那么回想之前的lca：我們發(fā)現(xiàn)第一種走法就是u->lca,lca->v.第二種走法就是u->v,但是lca(u,v)=v再考慮到每次其實是在走深度差，dis=d[u]+d[v]-2*d[lca]求法最一般的做法就是倍增，這個做法常數(shù)較大，但是非常直觀易懂。考慮最簡單的做法，就是一層一層往上提，就像我之前“定義”的一樣。這種東西多半都可以通過倍增加速，每次提不會傻乎乎的提升1，而是用2的倍數(shù)。具體的實現(xiàn)可以參考代碼講，我認(rèn)為倍增lca的代碼非常直觀。一種常數(shù)更小的求解方法之前的求解辦法是每次跳2的冪次，保證了復(fù)雜度是O(logn)還有一種辦法就是將樹鏈進(jìn)行劃分，選取size最大的子樹作為重兒子連成重鏈，每一段重鏈可以直接跳可以證明重鏈不會超過logn條，因此總復(fù)雜度依然是O(logn)但是和前者相比，一次預(yù)處理可以快速回答所有詢問，而且常數(shù)非常優(yōu)秀。樹鏈剖分其實非常簡單，但是是提高組內(nèi)容，有興趣的同學(xué)可以去看nzhtl1477老師的提高組講課。LCA的簡單應(yīng)用例題P2912[USACO08OCT]牧場散步PastureWalking預(yù)處理到根結(jié)點的距離，然后直接按照之前的公式計算即可（我不會說示例的代碼就是這題的）LCA的簡單例題【bzoj1787】[Ahoi2008]Meet緊急集合求出三個點兩兩的lca，直接計算最優(yōu)解即可。還有一種做法就是如果有兩個lca相等，那么集合點就是下一個。圖論圖的一些性質(zhì)：多對多沒有太多性質(zhì)了。樹是一種特殊的圖。圖的最短路徑最簡單的算法：floyd算法，也是考綱內(nèi)唯一的多源最短路徑算法。算法的核心非常簡單，枚舉中間中轉(zhuǎn)節(jié)點，暴力枚舉完就完成了所有最短路的計算。圖的最短路徑有的最短路徑問題是固定起點的，稱為單源最短路。這類問題有三種算法：bellman-Ford,Dijkstra,SPFA其中第一種比較慢，第二種很不錯但是不能出現(xiàn)負(fù)權(quán)，第三種復(fù)雜度比較玄學(xué)但是總體表現(xiàn)很快。我們講一下Dijkstra算法和SPFA算法。Dijkstra算法這類最短路徑算法的基礎(chǔ)：三角形不等式。具體而言就是反復(fù)利用三角形不等式進(jìn)行迭代，直到找到最優(yōu)解的過程。這個我覺得照著講義講非常好~SPFA算法是一種優(yōu)化過的Bellman-Ford算法。d[v]>=dis[u][v]所以d是單調(diào)不降的，這也是最短路徑算法的基礎(chǔ)。spfa的特點：只有當(dāng)前被更新的點才對狀態(tài)產(chǎn)生貢獻(xiàn)，用隊列維護(hù)所有有用狀態(tài)。對著代碼講可能比較好。spfa的其他東西用dfs實現(xiàn)的spfa如果未被訪問過直接dfs(v)即可。但是誠如上午所說，這類“最短”的問題，dfs存在一定的盲目性，所以dfs效率較差，無法通過luogu的模板數(shù)據(jù)。dfs-SPFA的應(yīng)用可以用來快速的找負(fù)環(huán)。找到了可增廣，并且已經(jīng)在dfs棧里面的節(jié)點，證明找到了負(fù)環(huán)。那么bfs實現(xiàn)的spfa如何尋找負(fù)環(huán)呢？如果一個點進(jìn)隊次數(shù)達(dá)到n，證明它在一個負(fù)環(huán)里面。顯然前者效率更為優(yōu)秀。一些簡單的應(yīng)用2017計算之道復(fù)賽D.百度地圖導(dǎo)航最小生成樹算法一般而言最多人寫的最小生成樹是Kruskal，而且非常簡單。前置技能：并查集。簡單介紹算法原理：首先我們證明一個定理：邊權(quán)最小的邊肯定在最小生成樹上。將他加入最小生成樹。如果一條邊連接的兩個點已經(jīng)被聯(lián)通，那么這條邊肯定不選，因為我們已經(jīng)有了更優(yōu)的方案。不斷重復(fù)上述過程，直到我們得到了最小生成樹。最小生成樹的應(yīng)用P2330[SCOI2005]繁忙的都市考慮Kruskal的性質(zhì)，我們最后加入的邊肯定是最大的，而且在所有可能方案中，它一定是最小的。所以直接Kruskal算一遍即可。拓?fù)渑判蛏妒峭負(fù)渑判蚰?？先介紹DAG（有向無環(huán)圖），這個自然是字面意思。每次選擇入度為0的點，把它刪掉，不斷重復(fù)，直到刪完了整張圖，這就叫拓?fù)渑判?，得到的序列就是拓?fù)湫?。顯然拓?fù)湫虿晃ㄒ煌負(fù)渑判虻囊饬x例子：選課。比如某些東西的學(xué)習(xí)順序：想學(xué)習(xí)splay就得先學(xué)會二叉排序樹，二叉排序樹可以直接學(xué)，線段樹可以直接學(xué)，想學(xué)會segment-tree-beats!就得先學(xué)會線段樹，想學(xué)會Link-Cut-Tree就得先學(xué)會splay和樹鏈剖分……我們發(fā)現(xiàn)事件（或者節(jié)點）之間存在著依賴關(guān)系，也就是我們必須按照一定的順序做某些事情，這就是拓?fù)渑判?。拓?fù)渑判虻膶崿F(xiàn)用bfs進(jìn)行拓?fù)渑判颉Ｏ劝讶攵?0的點全部壓入隊列，然后每次拓展，把新的ind[v]=0的點放入隊列。對著代碼講。深入談一些拓?fù)渑判虻男再|(zhì)拓?fù)渑判蚺c動態(tài)規(guī)劃。動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移是要滿足拓?fù)湫蜣D(zhuǎn)移的，本質(zhì)上所有的動態(tài)規(guī)劃是一邊拓?fù)渑判蛞贿呌嬎惴桨?。樹的拓?fù)湫驑涫翘焐鷿M足拓?fù)湫虻慕Y(jié)構(gòu)。很多樹上問題的統(tǒng)計都是從下向上的，本質(zhì)上是把樹在進(jìn)行拓?fù)渑判?。例題NOIP2013車站分級暴力拓?fù)渑判颍B邊無法承