1、樹,1,2,基礎(chǔ)知識(shí),2,2,樹的定義,樹是連通且無環(huán)的無向圖 等價(jià)條件： 連通，且含有n個(gè)點(diǎn)、n-1條邊 任意兩點(diǎn)間恰有一條路徑,3,2020/6/22,無根樹,滿足上述定義、沒有其他限制 每個(gè)節(jié)點(diǎn)的地位是相同的 當(dāng)做普通的無向圖來處理,4,2020/6/22,有根樹,在定義的基礎(chǔ)上、指定一個(gè)節(jié)點(diǎn)為“根” 相比無根樹，有根樹更多地利用樹的性質(zhì)，組織結(jié)構(gòu)更加清晰 樹上的問題一般先轉(zhuǎn)化成有根樹再解決。,5,2020/6/22,有根樹的結(jié)構(gòu),描述有根樹的結(jié)構(gòu)： 若a在b到根的路徑上(如a=1,b=3; a=4,b=6)， 則稱a是b的祖先、b是a的子孫 特殊地，若a是b的祖先、且a和b相鄰(如a=

2、1,b=4; a=5,b=6)，則稱a是b的父親(父節(jié)點(diǎn))，b是a的兒子(子節(jié)點(diǎn)) 一個(gè)節(jié)點(diǎn)及其所有子孫節(jié)點(diǎn)組成一棵子樹 深度：根據(jù)需要定義根的深度為0或1；每走過一條向下的邊深度+1,6,2020/6/22,有根樹的存儲(chǔ),方法一：除了根沒有父親，所有節(jié)點(diǎn)都有唯一的父親。記錄每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)即可。缺點(diǎn)是不能從根開始遍歷整棵樹 應(yīng)用：并查集 方法二：(同普通的無向圖)用鄰接表存儲(chǔ)。從根開始dfs時(shí)得到每個(gè)點(diǎn)的父節(jié)點(diǎn)，除了父節(jié)點(diǎn)外相鄰的節(jié)點(diǎn)就是子節(jié)點(diǎn)。 應(yīng)用：(很多OI題中)只知道樹邊的兩個(gè)端點(diǎn)、不知道父子關(guān)系的情況,7,2020/6/22,基本問題,8,2,樹的直徑,給定一棵樹，每條邊的長(zhǎng)度為1

3、。 定義樹的直徑是樹上最長(zhǎng)的路徑。注意直徑可能有多條。 求直徑的長(zhǎng)度。,9,2020/6/22,樹的直徑,暴力O(n2) 枚舉路徑的一個(gè)端點(diǎn)x，dfs求出所有從x開始的路徑的長(zhǎng)度。,10,2020/6/22,樹的直徑,經(jīng)典算法一：簡(jiǎn)單樹形dp 考慮一棵樹的直徑與其根的關(guān)系，它要么經(jīng)過根，要么完全在根的一個(gè)子樹里。 如果直徑經(jīng)過根，考慮根將直徑分成的兩個(gè)部分，它們是子樹中從根向下的最長(zhǎng)的兩條路徑。 對(duì)于直徑不經(jīng)過根的情況遞歸求解即可。 令fi為從i向下的最長(zhǎng)路徑長(zhǎng)度，dfs過程中統(tǒng)計(jì)即可。,11,2020/6/22,樹的直徑,#include using namespace std; const

4、 int MAXN = 100007; vector EMAXN; int n, ans; int f(int x, int fa) int ret = 1, m1 = 0, m2 = 0; for (int i = 0; i Ex.size(); +i) if (Exi != fa) int r = f(Exi, x); if (ret r + 1) ret = r + 1; if (m1 r) m2 = m1, m1 = r; else if (m2 n; for (int i = 1; i u v; Eu.push_back(v); Ev.push_back(u); f(1, -1);

5、printf(%dn, ans); return 0; ,12,2020/6/22,樹的直徑,經(jīng)典算法二： 隨便選一個(gè)點(diǎn)x，求出距離x最遠(yuǎn)的一個(gè)點(diǎn)y，然后再求出距離y最遠(yuǎn)的一個(gè)點(diǎn)z，yz一定是一條直徑。 兩遍dfs即可。 證明：關(guān)鍵是證明y一定是某一條直徑的一個(gè)端點(diǎn)。 用反證法。(?) 類似地也可以證明所有直徑都相交 (?),13,2020/6/22,樹的中心,對(duì)于一棵樹，定義r(x)為離x最遠(yuǎn)的點(diǎn)到x的距離；定義樹的中心為滿足r(x)最小的點(diǎn)x。 給定一棵樹，求它的中心。 所有直徑都經(jīng)過中心。可以用反證法證明。 (?) 中心是任意一條直徑的中點(diǎn)。對(duì)于直徑上有偶數(shù)個(gè)點(diǎn)的情況存在兩個(gè)中心。 (?

6、),14,2020/6/22,樹的重心,對(duì)于一棵樹，定義w(x)為將x作為根時(shí)、x最大的子樹的大小。定義樹的重心為滿足w(x)最小的點(diǎn)x。 給定一棵樹，求它的重心。 暴力O(n2) 枚舉每一個(gè)x、O(n)求出x所有子樹的size 如何優(yōu)化？,15,2020/6/22,樹的重心,首先任意指定一個(gè)根。不妨設(shè)為節(jié)點(diǎn)1。 接下來需要考慮：在指定1為根的情況下如何計(jì)算w(x)？ 容易看出x的子樹分為兩種：x下面的子樹 ，以及x上面包含1的部分 包含1的部分可以用n-size(x)來獲得 dfs一遍算出所有子樹大小即可,16,2020/6/22,樹的重心,結(jié)論：若x為樹的重心，則w(x)n/2 同樣用反證

7、法可證。 (?) 當(dāng)w(x)=n/2時(shí)恰有相鄰的兩個(gè)重心，其他情況下重心唯一。 畫張圖就能看出來。,17,2020/6/22,最近公共祖先,給定一棵有根樹，回答若干詢問，每次詢問兩個(gè)點(diǎn)a,b的最近公共祖先(LCA)。 不難想到的暴力做法：將ab中較深的向根移到同一深度；然后一起一步一步向根移動(dòng)，直到兩者重合。 優(yōu)化：用倍增加速這個(gè)過程。,18,2020/6/22,最近公共祖先,預(yù)處理：記upxi(i=0.logn)為從x向根移動(dòng)2i步到達(dá)的位置(如upx0就是x的父親)。如果移動(dòng)到了根以上的位置不妨令為0。 有遞推式 uprooti=0; upx0=fax; upxi=upupxi-1i-1;

8、 可以在O(nlogn)時(shí)間內(nèi)預(yù)處理。,19,2020/6/22,最近公共祖先,求a,b兩點(diǎn)的LCA： 首先將a,b提到同一深度：不妨設(shè)a當(dāng)前比b深，從大到小枚舉步長(zhǎng)2i，若b不比upai深則更新a。這里i=0.logn，復(fù)雜度O(logn) 若此時(shí)a=b則返回結(jié)果(b) 從大到小枚舉步長(zhǎng)2i，若upai!=upbi則更新a,b。這里i=0.logn，因此復(fù)雜度O(logn) 最后答案即為當(dāng)前a/b的父節(jié)點(diǎn)，即upa0,20,2020/6/22,最近公共祖先,const int logn = 18; int LCA(int a, int b) if (depa = 0; -i) if (dep

9、upai = 0; -i) if (upai != upbi) a = upai, b = upbi; return upa0; ,21,2020/6/22,簡(jiǎn)單的樹上統(tǒng)計(jì),給定一棵樹，有邊權(quán)，每次詢問兩個(gè)點(diǎn)的距離。 n, q 100000 任意指定一個(gè)根，求出每個(gè)點(diǎn)i到根的路徑的邊權(quán)和sumi。 對(duì)于詢問(x,y)，求出LCA(x,y)=a，則答案為sumx+sumy-2*suma 單次詢問復(fù)雜度O(logn),22,2020/6/22,簡(jiǎn)單的樹上統(tǒng)計(jì),給定一棵樹，有邊權(quán)，每次詢問兩點(diǎn)之間的最大值。 n, q 100000 類比RMQ。令MAXxi為從x向上2i個(gè)數(shù)的最大值，用類似up的方式

10、預(yù)處理。 詢問時(shí)一邊求LCA一邊求答案即可。,23,2020/6/22,樹同構(gòu),給出兩棵節(jié)點(diǎn)數(shù)相同的有根樹，問它們是否同構(gòu)。 基本思想是樹哈希：設(shè)計(jì)一種對(duì)于樹的哈希函數(shù)，并用哈希值相等作為判定樹同構(gòu)的依據(jù)。 下面給出一個(gè)較為合理的哈希函數(shù)作為參考： hashx=(ap xor H1 mod q)p xor H2 mod q)xor Hk mod q)b mod q 其中H1.Hk是對(duì)x的所有子樹的hash值從小到大排序的結(jié)果。排序能夠避免子樹的順序不同造成hash的差異。,24,2020/6/22,題目選講,25,2,BOOSTER,給定一棵有根樹，有邊權(quán)。 初始時(shí)只有根和葉子是關(guān)鍵點(diǎn)。 你可以花費(fèi)1個(gè)代價(jià)把一個(gè)節(jié)點(diǎn)變成關(guān)鍵點(diǎn)。 要求花費(fèi)最小的代價(jià)，使得對(duì)于所有從葉子到根的路徑中，任意相鄰兩個(gè)關(guān)鍵點(diǎn)的距離不超過給定的k。 n105 從葉子向上貪心,26,2020/6/22,GALLERY,給定一棵二叉樹，每條邊有通過時(shí)間ti，每個(gè)點(diǎn)有wi件物品。每取一件物品需要花費(fèi)5個(gè)單位時(shí)間。要求從根出發(fā)，花費(fèi)總時(shí)間不超過k、且最后回到根，獲得的物品數(shù)量最大。 N100, ti20, wi20, k600 較簡(jiǎn)單的樹上背包,27,2020/6/22,PARTY,給定一棵樹，求最大點(diǎn)權(quán)獨(dú)立集。 N100 樹形dp，dpx0/1表示子樹x、取不取x,28,2