夏令營(yíng)集訓(xùn)濰坊昌邑一中show

1、樹勝利一中 王子昱概要定義 & 性質(zhì)樹的遍歷Dfs序, Bfs序 & 歐拉序LCA問題樹形DP*樹分治題目選講定義 & 性質(zhì)定義(之一):聯(lián)通、無環(huán)的無向簡(jiǎn)單圖每個(gè)頂點(diǎn)都是割點(diǎn)，每條邊都是割邊NOI07 追捕盜賊在樹上添加一條邊會(huì)得到一個(gè)環(huán)在生成樹相關(guān)的問題中很有用的性質(zhì)樹是二分圖關(guān)鍵字N個(gè)頂點(diǎn)，n-1條邊的聯(lián)通圖任意兩點(diǎn)間有且只有一條路徑每個(gè)點(diǎn)向東至多連一條邊(NOI2008道路設(shè)計(jì))Et cetera樹的遍歷深度優(yōu)先遍歷和圖的dfs一致先序遍歷，中序遍歷，后序遍歷DFS序DFS序深度優(yōu)先遍歷得到的序列:Dfs(x)list.push_back(x)For every child ch of

2、 x:Dfs(ch)List.push_back(x)abeeffbcgghhiicdjjda()()()()()()DFS序 : 性質(zhì)一棵子樹對(duì)應(yīng)一段連續(xù)的序列abeeffbcgghhiicdjjda或者是abefcghidja例題給定一棵節(jié)點(diǎn)帶權(quán)的樹兩種操作A I delta：以I為根的子樹內(nèi)節(jié)點(diǎn)權(quán)值+deltaQ I: 求以I為根的子樹的權(quán)值和樹狀數(shù)組|線段樹維護(hù)dfs序abeeffbcgghhiicdjjda()()()()()()DFS序 : 性質(zhì)改動(dòng)一下剛才的代碼:Dfs(x)list.push_back(+x)For every child ch of x:Dfs(ch)List

3、.push_back(-x)考慮這個(gè)序列從+a到+g的和+a +b +e e +f f b +c +g正負(fù)抵消后就是從a到g的路徑！abeeffbcgghhiicdjjda()()()()()()例題一棵節(jié)點(diǎn)帶權(quán)的樹，兩種操作A I delta: 點(diǎn)i的權(quán)增加deltaQ I j: 輸出從i到j(luò)的路徑上點(diǎn)的權(quán)值和直接套用剛才的方法？abeeffbcgghhiicdjjda()()()()()()例題反例：從e到c+e e b +ce-c a-e + a-c weighta(+a +b +e) + (+a +b +e e +f f b +c) aQ(u, v) = Q(w, u) + Q(w,

4、v) weightw,W = LCA(u,v)什么是LCA？一會(huì)再說樹狀數(shù)組|線段樹維護(hù)DFS序abeeffbcgghhiicdjjda()()()()()()廣度優(yōu)先遍歷圖的BFS使用隊(duì)列BFS序BFS序廣度優(yōu)先遍歷得到的序列Bfs(x)Que.push(x)While not Que.empty()Y = que.pop()List.push_back(y)For every child ch of yque.push(ch)同一深度的節(jié)點(diǎn)形成一個(gè)連續(xù)的區(qū)間Algorithm Engagement 2010 Firm這道題涉及的一些東西超綱了= =abcdefghij歐拉序列以根為起點(diǎn)的歐

5、拉回路應(yīng)用：LCA(最近公共祖先)問題：LCA(u,v)表示u和v的深度最大的公共祖先圖中LCA(g,h)=c，LCA(g,j)=a給歐拉序列里的每個(gè)點(diǎn)加權(quán)，點(diǎn)i的權(quán)值是i的深度于是u, v的LCA是歐拉序列中u, v之間深度最小的點(diǎn)證明？abebfbacgchcicadjdae.g.abebfbacgchcicadjda0 LCA(g,h)=c樹形DPSPOJ PT07X樹的最小覆蓋最小覆蓋：選出點(diǎn)集的最小子集使得每條邊至少有一個(gè)端點(diǎn)在該點(diǎn)集中二分圖：轉(zhuǎn)化為匹配f1i表示選擇i時(shí), 以i為根的子樹的最小覆蓋; f0i表示不選i時(shí)的最小覆蓋轉(zhuǎn)移SPOJ PT07Z樹的最長(zhǎng)路一種優(yōu)美的貪心算法兩

6、遍dfs應(yīng)用了樹的獨(dú)特性質(zhì),不可推廣DP任意選定一個(gè)根最長(zhǎng)路一定是從一個(gè)點(diǎn)向下擴(kuò)展出的最長(zhǎng)路f和次長(zhǎng)路g （如果有）的和 沿最短路走到該點(diǎn)，再?gòu)母狞c(diǎn)沿次短路繼續(xù)走只需要維護(hù)這兩個(gè)量就可以了最長(zhǎng)路 : 推廣求出每個(gè)頂點(diǎn)出發(fā)的最長(zhǎng)路定根之后，計(jì)算出從每個(gè)點(diǎn)向下的最長(zhǎng)路f和次長(zhǎng)路g點(diǎn)u的最長(zhǎng)路可能是直接向下的(fu)，也可能是向上之后再向下(設(shè)為hu)怎么計(jì)算H ？最長(zhǎng)路 : 推廣樹形DP的推廣不一定是在樹上進(jìn)行的DpSDOI2010 Area題意：最大權(quán)獨(dú)立集30%數(shù)據(jù)：圖是一棵樹Dp70%數(shù)據(jù)：圖是基環(huán)+外向樹的結(jié)構(gòu)如果只有環(huán)該怎么做？100%數(shù)據(jù)：仙人掌樹形DP大多數(shù)題目的套路是一樣的自底向上

7、自頂向下在狀態(tài)中維護(hù)額外的信息點(diǎn)分治題目選講樹網(wǎng)的核NOIP2007, modified給定一棵邊帶權(quán)的樹，求出一條長(zhǎng)=W的路徑，使得到路徑距離最大的點(diǎn)的距離最小N = 300000Next樹網(wǎng)的核Hint證明：最優(yōu)方案可以是直徑的一段直徑的優(yōu)美性質(zhì)Next樹網(wǎng)的核Solution求出直徑對(duì)直徑上的點(diǎn)，計(jì)算disLeftx=x左端所有結(jié)點(diǎn)到x距離的最大值disRightx 同類disDev x=到直徑的入口為x的所有點(diǎn)與x距離的最大值枚舉+二分或單調(diào)隊(duì)列計(jì)算答案O(NlogN)或O(N)NextSPOJ PT07B給定一棵樹，找到它的最大的滿足以下條件的子樹：所有度大于2的點(diǎn)至多被兩個(gè)度大于1

8、的點(diǎn)連接.N=100000NextSPOJ PT07BSolution“毛毛蟲”如果毛毛蟲沒有足？最長(zhǎng)路“足”的數(shù)目可以被附加到點(diǎn)上！設(shè)點(diǎn)u的權(quán)值為degu-1去掉所有權(quán)=0的點(diǎn)帶權(quán)最長(zhǎng)路NextSPOJ PT07F樹的最小路徑覆蓋選出數(shù)目最少的不相交路徑，使得每一個(gè)節(jié)點(diǎn)都在一條路徑上N=100000NextSPOJ PT07FsolutionNextSPOJ PT07I一棵樹上有m個(gè)螞蟻窩螞蟻i會(huì)在時(shí)刻Ti從窩Si里出來，以速度vi向窩Sj出發(fā)問有多少對(duì)螞蟻在路上相遇M=1000, N 稍微提一下常見方法點(diǎn)分治邊分治塊分治(樹塊剖分)鏈分治(樹鏈剖分)Next點(diǎn)分治選擇一個(gè)點(diǎn)將無根樹轉(zhuǎn)為有根樹遞歸處理去掉根之后的每一棵子樹例題給定一棵樹，點(diǎn)上帶權(quán)求出所有長(zhǎng)度=k的路徑Next點(diǎn)分治 Cond選一個(gè)根之后，路徑可以分為經(jīng)過根和不經(jīng)過根的兩種經(jīng)過根的情況計(jì)算出當(dāng)前子樹中所有點(diǎn)到根的距離,用排序+掃描的方法求出和 deprootb)Res = max(res, dataa) / dataa表示到塊根的最大權(quán)值A(chǔ) = prerootaElseRes = max(res, datab)B = prerootbWhile (a != b)If (depa depb