清北第二天，感受到了來自這個(gè)世界的不友善，大概把沒聽過不會(huì)的“名詞”記錄下來就已經(jīng)一面了，然后被大佬說這都是最基礎(chǔ)的東西，就很皮，那就趁別人練習(xí)字符串的題的時(shí)候，來寫波博客了，倒不是不想寫，（MD這么快就KMP，Hash，Manacher，AC自動(dòng)機(jī)，Tire樹，我毛都不會(huì)啊沒法寫啊，講的巨難，詳細(xì)也聽不懂啊，上來一個(gè)指針就蒙了）
不扯沒意思的，從早上開始積累的問題慢慢總結(jié)吧。
1、倍增：第一次聽到這個(gè)詞是懵逼的，然后什么樹上倍增的直接讓我就傻逼了，實(shí)際上在之前有次上課的時(shí)候，老師提了一句話，現(xiàn)在想起來倒是發(fā)現(xiàn)體現(xiàn)了倍增的思想，倍增倍增，成倍增加，就是在算Nm的時(shí)候，可以直接把m拆成2*4*8*16*32*……，那么這個(gè)2 4 8 16 32 這一連串就體現(xiàn)了倍增的思想，加快了化學(xué)反應(yīng)速率算法的的速度，提高效率，避免了不必要的重復(fù)計(jì)算。
2、樹：可謂有各種奇葩的不奇葩的麻煩的難的樹，今天講的大概有如下幾個(gè)幾百個(gè)：生成樹、最大生成樹、最小生成樹、LCA最近公共祖先、線段樹、樹狀數(shù)組、樹上倍增、有根樹、重構(gòu)樹、虛樹、樹剖等……
一個(gè)一個(gè)來：
生成樹：如果連通圖G的一個(gè)子圖是一棵包含G的所有頂點(diǎn)的樹，則該子圖稱為G的生成樹(SpanningTree)。生成樹是連通圖的包含圖中的所有頂點(diǎn)的極小連通子圖。
最小生成樹：一個(gè)有 n 個(gè)結(jié)點(diǎn)的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個(gè)結(jié)點(diǎn)，并且有保持圖連通的最少的邊。即最小權(quán)重生成樹，每個(gè)邊所帶的權(quán)重值的和最小即為最小生成樹。
嚴(yán)格次小生成樹：
最大生成樹：與最小生成樹相對(duì)，每個(gè)邊所帶的權(quán)重值和最大即為最大生成樹。
