2023年天梯賽那道L3-2完美樹賽后我在補題群里聽到最多的抱怨就是明明想到了樹形DP怎么一交就T。這題卡人的地方真不在DP思路上而在于你有沒有意識到——奇偶性這把刀已經把狀態(tài)空間砍得只剩巴掌大。你要是還按常規(guī)套路開一個寬度為子樹大小的背包去卷那必然是O(n2)的復雜度n一旦上到10?級別直接原地炸掉。我當時的心理預期也差不多看到樹形DP四個字就條件反射地想背包結果被這道題結結實實上了一課。這篇就把我從讀題、建模、推轉移到寫出一個能跑的O(n log n)解法的完整過程攤開講。關鍵詞先擺在這兒天梯賽、樹形DP、完美樹、L3_2、01最大/小價值。不管你是剛打完這屆天梯賽想復盤還是在準備下一屆的L3沖刺或者單純想搞明白01最大/小價值這種說法到底指什么下面的內容應該都能給你點東西。1. 完美樹的約束到底完美在哪1.1 一句差值不超過1鎖死了整棵樹的形態(tài)題目給的約束很短經過任意次改色之后對于樹上每一個節(jié)點以它為根的子樹里兩種顏色的節(jié)點數(shù)量差的絕對值不能超過1。就這么一句話沒有一個多余的形容詞但它對整棵樹施加的是層層嵌套的強約束。關鍵在于它是對每個節(jié)點都成立而不是只看根節(jié)點。這意味著你不能只顧著讓整棵樹平衡還得保證任意一個局部子樹都是平衡的。很多人第一反應是那不就是讓每個子樹盡量平分嗎方向沒錯但盡量這個詞太松了。絕對值不超過1意味著差值只能落在-1、0、1三個值上一個都不多。子樹節(jié)點數(shù)如果是偶數(shù)那兩種顏色的數(shù)量必須嚴格相等差為0沒有商量的余地子樹節(jié)點數(shù)如果是奇數(shù)差只能是1或者-1二選一。你看約束一寫清楚可選空間立刻從一個連續(xù)的整數(shù)區(qū)間塌縮成了最多兩個離散取值。這就是這道題第一個反直覺的地方題目看起來是讓你去做平衡優(yōu)化實際上它是在逼你做離散取值的選擇。再往深一層想這種嵌套約束還帶著一種自下而上的傳遞性。一個節(jié)點的子樹是否完美取決于它所有兒子的子樹是否完美再加上它自己那一票。你在整棵樹的最底層把每棵小子樹都調完美了上面一層才有可能完美。這天然就是后序遍歷的節(jié)奏也是樹形DP的典型信號。但請注意不是所有自下而上的題都要套背包這道題就是那個例外。1.2 子樹大小的奇偶性才是隱藏的主角我真正想強調的一點是題面里從頭到尾沒提奇偶兩個字但奇偶性才是這題的解題鑰匙。你想一棵子樹有sz個節(jié)點分成兩種顏色數(shù)量分別是x和yxysz要求|x-y|≤1。那么這個差值|x-y|的奇偶性其實和sz的奇偶性是綁死的。因為x-y x-(sz-x) 2x-sz2x是偶數(shù)所以x-y的奇偶性完全由sz決定。于是可以推出一個非常干凈的結論子樹大小為偶數(shù)合法差值只能是0因為2x-sz為偶數(shù)且要求落在[-1,1]只有0滿足。子樹大小為奇數(shù)合法差值只能是1或-1因為此時2x-sz為奇數(shù)[-1,1]里的奇數(shù)只有±1。這個結論直接決定了一棵子樹對外能貢獻什么。偶數(shù)大小的子樹對外只有一個姿態(tài)不偏不倚差為0奇數(shù)大小的子樹對外有兩個姿態(tài)多一個A色或者多一個B色。換句話說一個奇數(shù)子樹的全部對外信息就是1還是-1這正是關鍵詞里01的味道——每個奇數(shù)子樹本質上是一個二選一開關。我在補題的時候特意停下來琢磨了一下這個性質越想越覺得精妙。出題人把平衡這個看似連續(xù)優(yōu)化的東西通過取整和絕對值硬生生壓成了一個離散二選一問題。你要是沒意識到這層就容易寫出一個又大又慢的背包一旦意識到了整道題的結構瞬間清爽。1.3 為什么這題不適合無腦開大數(shù)組的樹形背包順著常規(guī)思路你會很自然地定義dp[u][delta]delta表示子樹u內兩種顏色的數(shù)量差。問題來了delta的取值范圍是多少如果你不做任何剪枝delta可以取到[-sz[u], sz[u]]里的所有值那這就是一個標準的樹形背包合并兩個子樹是兩個數(shù)組的卷積復雜度是O(n2)。但這個范圍其實是虛的。因為子樹u自己這一層的約束要求|delta|≤1而delta又由子節(jié)點的貢獻加和而來。也就是說你辛辛苦苦枚舉的絕大多數(shù)delta值最終都因為不滿足|delta|≤1被丟棄了。既然如此為什么不一開始就把范圍掐死在{-1,0,1}呢答案是可以的但前提是你要處理好中間過程可能短暫超出范圍的情況——加一個大正數(shù)再加一個大負數(shù)最后可能回到[-1,1]。這個細節(jié)我在第3節(jié)會掰開講?？傊Y論是這題的最優(yōu)解不是背包卷積而是一次排序加前綴和時間復雜度直接降到O(n log n)甚至O(n)。2. dp狀態(tài)怎么定三種差值一個節(jié)點2.1 單點改色代價的建模方式先把題目的輸入模型固定下來。每個節(jié)點i有一個初始顏色c_i以及把它最終定成顏色0的代價cost0[i]、定成顏色1的代價cost1[i]。這里的代價含義是不管你原來是啥色只要最終變成目標色就付對應的錢。這么建模的好處是它足夠通用——如果題目給的是翻轉一次花x那你也能換算成保持原色花0、翻成另一色花x?；谶@個模型單個節(jié)點的選擇其實就兩種最終定成0付cost0[i]最終定成1付cost1[i]。節(jié)點自己對子樹的差值貢獻是多少如果它定成0那它對顏色0的個數(shù)減顏色1的個數(shù)這個差值的貢獻就是1定成1就是-1。我們把節(jié)點自己的貢獻記成w定成0時w1定成1時w-1。就這么簡單一個節(jié)點全部的信息就是選0還是選1以及各自多少錢又是二選一。到這里你會發(fā)現(xiàn)整道題從根到葉處處是二選一。節(jié)點自己二選一奇數(shù)子樹對外二選一偶數(shù)子樹干脆沒得選。這種處處是開關的結構正是01最大/小價值這個關鍵詞的來源——我們要做的就是在這些開關里挑出總代價最小的那套組合。2.2 子節(jié)點能給出的貢獻只有0或±1現(xiàn)在看一個節(jié)點u它有若干個子節(jié)點v。每個子節(jié)點v自己也是一棵完美的子樹它能給u貢獻一個差值d_v。根據(jù)第1節(jié)的結論如果sz[v]是偶數(shù)那么d_v只能是0這個子節(jié)點在差值這件事上就是個啞巴它不改變總的差值但它有自己的代價dp0[v]。如果sz[v]是奇數(shù)那么d_v只能是1或者-1對應代價分別記作dp1[v]和dpm1[v]。我們定義三個值來描述子樹vdp0[v]表示v子樹完美且差值為0的最小代價dp1[v]表示差值為1dpm1[v]表示差值為-1。對于偶數(shù)子樹只有dp0[v]有意義對于奇數(shù)子樹只有dp1[v]和dpm1[v]有意義。你甚至可以認為無效的那些狀態(tài)是無窮大這樣統(tǒng)一處理起來更省心。這一步是整個建模的核心。它把每個子節(jié)點壓縮成了一個要么0、要么在±1里挑一個的貢獻單元。想想看一棵可能有幾萬個節(jié)點的子樹對外居然只用一個三值狀態(tài)就能概括這種信息壓縮正是解這道題的爽點所在。你要是沒做這層壓縮dp數(shù)組的維度就會失控。2.3 轉移方程的完整推導把節(jié)點u的所有子節(jié)點貢獻加起來再加上u自己的貢獻w就得到u子樹的總差值delta w Σ d_v約束要求最終|delta|≤1。同時u子樹的節(jié)點數(shù)是sz[u] 1 Σ sz[v]所以delta的奇偶性也被sz[u]鎖死sz[u]為偶數(shù)則delta0為奇數(shù)則delta±1。這兩個條件要同時滿足缺一不可。統(tǒng)計一下假設u有m個奇數(shù)大小的子節(jié)點其余是偶數(shù)子節(jié)點。偶數(shù)子節(jié)點貢獻固定為0只貢獻代價m個奇數(shù)子節(jié)點每個選1或-1。設其中有p個選了1那么就有(m-p)個選了-1于是Σd_v p - (m-p) 2p - m。代進delta的表達式delta w 2p - m我們要讓這個值落在允許的集合里。給定w由u選0還是選1決定和m每個合法的delta都反推出一個唯一確定的pp (delta - w m) / 2注意這里p必須是[0,m]之間的整數(shù)否則這個delta對這個顏色的選擇就是不可達的。整個轉移就變成了對每種合法組合算出一個必須恰好選p個子節(jié)點取1的方案然后求最小代價。你看一堆看起來復雜的組合被約束一逼就只剩選幾個這一個自由度了。3. 01最大/小價值合并時的貪心選法3.1 把選哪些子樹取1變成一個排序問題現(xiàn)在問題被徹底簡化成一個組合優(yōu)化小問題有m個奇數(shù)子節(jié)點每個子節(jié)點v如果取-1代價是dpm1[v]如果取1代價是dp1[v]?，F(xiàn)在要求恰好選p個取1怎么選總代價最小做法非常樸素先假設全取-1總代價base Σ dpm1[v]這一定是可行的基線。然后定義每個子節(jié)點從-1切換到1的增量delta_v dp1[v] - dpm1[v]這個增量可能為正切過去更貴也可能為負切過去更便宜說明這棵子樹本身就更傾向于1。要恰好切p個過去我們當然希望總增量最小所以把所有的delta_v排個序取最小的p個加起來再疊到base上。這就是最優(yōu)方案。這里要提醒一個容易被忽略的點即使某些delta_v是正數(shù)只要p大于負增量的個數(shù)你也必須捏著鼻子去切那些正增量的子樹因為你沒有選擇——p是約束定死的不是隨便挑。很多人初學時總想著只切負的、正的不切但那會導致實際取1的個數(shù)不足p最終delta不滿足約束答案是錯的。3.2 為什么取最小的p個增量就是最優(yōu)有人可能會問取最小的p個delta憑什么保證最優(yōu)理由其實很直接?？偞鷥r可以寫成總代價 base Σ(被選中切換的delta_v)base是定死的所以要最小化總代價等價于最小化被選中切換的那p個delta_v之和。在m個增量里選p個使其和最小當然就是排序后取最小的那p個。這是一個無爭議的貪心不需要什么證明技巧。不過這里藏著一個小陷阱我要專門點一下如果你為每個節(jié)點枚舉所有可能的delta0、1、-1然后想用背包去卷那你就又掉回大數(shù)組的老路了。正確地利用p唯一確定這個性質才是把復雜度降下來的關鍵。每個節(jié)點u在固定顏色w和固定目標delta之后p是唯一的所以你根本不需要背包只需要一次排序加一次前綴和。子節(jié)點之間是相互獨立的它們的delta_v互不影響排序貪心完全成立。3.3 復雜度從O(n2)降到O(n log n)來算一筆賬。對每個節(jié)點u我們要對它的所有奇數(shù)子節(jié)點做一次排序。一個節(jié)點u的排序規(guī)模是它的奇數(shù)子節(jié)點個數(shù)m_u。所有節(jié)點加起來Σm_u不會超過節(jié)點的總數(shù)每個節(jié)點最多作為某個父節(jié)點的一個子節(jié)點被統(tǒng)計一次所以總的排序元素個數(shù)是O(n)。即使每個子樹單獨排序總復雜度也就是O(n log n)——而且還不是那種最壞情況的n log n實際跑起來很快因為每個節(jié)點的m_u通常很小。對比一下樸素背包每個節(jié)點合并子節(jié)點時數(shù)組長度是子樹大小量級父節(jié)點合并多個子節(jié)點會有卷積開銷總的復雜度是O(n2)n10?時是101?量級的操作穩(wěn)穩(wěn)超時。這就是為什么我說這題的關鍵不在樹形DP本身而在于你有沒有把狀態(tài)空間壓干凈。壓對了O(n log n)輕松過壓錯了再好的常數(shù)也救不回來。還有一個可以進一步優(yōu)化的點其實你根本不需要對每個節(jié)點完整排序因為你要的是最小的p個delta之和。如果m_u很小直接排就行如果m_u很大可以用std::nth_element找出第p小再求和理論上能到O(m_u)。不過實測下來排序的常數(shù)開銷更友好除非你被卡到極限否則std::sort完全夠用。提示增量數(shù)組里可能出現(xiàn)兩個子樹增量相等的情況這沒關系排序穩(wěn)定與否不影響最終求和結果取最小的p個值即可。4. 代碼落地與實現(xiàn)細節(jié)4.1 建圖與后序遍歷先把樹的存儲結構確定下來。既然是給一棵以1為根的有根樹鄰接表建無向圖然后從根做一次DFS即可。需要注意n在1e5甚至更大時遞歸DFS有爆棧風險穩(wěn)妥做法是寫一個迭代版的后序遍歷或者手動開棧、加大系統(tǒng)棧。我個人的習慣是n不超過2×10?時直接遞歸用編譯器的棧擴容參數(shù)兜底再大就寫迭代版本從根開始做一次BFS得到遍歷序再逆序處理天然就是后序。后序遍歷的順序至關重要因為節(jié)點u的轉移依賴所有子節(jié)點的dp值。逆BFS序從葉子往根是等價于后序的而且實現(xiàn)簡潔不涉及遞歸。我下面給的代碼用遞歸寫法邏輯更直觀你在實際提交時按自己的習慣改迭代即可。另外一個細節(jié)代價可能很大題目如果給的是1e9量級的代價n又是1e5總和可能到1e14必須用64位整數(shù)。我見過不止一個人在這題上寫int然后WA到懷疑人生檢查半天邏輯最后發(fā)現(xiàn)是溢出。4.2 dp數(shù)組的初始化與合并順序dp數(shù)組的定義dp0[u]、dp1[u]、dpm1[u]分別表示u子樹完美且總差值為0、1、-1的最小代價。初始化時全部設為無窮大然后枚舉u最終的顏色。對每個顏色col0或1基礎代價c cost_col[u]w (col0 ? 1 : -1)。然后收集所有的奇數(shù)子節(jié)點v把dpm1[v]累進base把dp1[v]-dpm1[v]放進增量數(shù)組偶數(shù)子節(jié)點直接把dp0[v]累進base。接著對增量數(shù)組排序、前綴和。然后枚舉目標差值delta ∈ {-1,0,1}用公式p (delta - w m)/2反推p檢查p是否在[0,m]內且為整數(shù)若是則用base prefix[p]更新對應狀態(tài)。這里一定要記得檢查整除和邊界p算出個負數(shù)或者小數(shù)說明這個delta對這組cnadidate不可達直接跳過。合并順序上沒什么講究因為子節(jié)點之間獨立先合并誰后合并誰無所謂。但要注意在枚舉顏色和delta時同一個目標狀態(tài)可能被兩種顏色同時更新到取min即可。4.3 完整代碼與逐段說明下面這份代碼可以直接作為模板參考注釋我寫得比較細方便你對照前面的推導看#include bits/stdc.h using namespace std; const long long INF (long long)4e18; int n; vectorvectorint g; vectorlong long cost0, cost1; // 定成0/1的代價 vectorlong long dp0, dp1, dpm1; // 三種差值狀態(tài) vectorint sz; void dfs(int u, int p) { sz[u] 1; long long base 0; vectorlong long delta; for (int v : g[u]) { if (v p) continue; dfs(v, u); sz[u] sz[v]; } // 子樹大小已經算好開始收集貢獻 for (int v : g[u]) { if (v p) continue; if (sz[v] % 2 0) { base dp0[v]; // 偶數(shù)子樹貢獻固定為0 } else { base dpm1[v]; // 先默認全取 -1 delta.push_back(dp1[v] - dpm1[v]); } } sort(delta.begin(), delta.end()); int m (int)delta.size(); vectorlong long pre(m 1, 0); for (int i 0; i m; i) pre[i 1] pre[i] delta[i]; dp0[u] dp1[u] dpm1[u] INF; for (int col 0; col 1; col) { long long c (col 0 ? cost0[u] : cost1[u]); int w (col 0 ? 1 : -1); for (int d -1; d 1; d) { int num d - w m; // num 2p if (num 0 || num 2 * m) continue; if (num % 2 ! 0) continue; int p num / 2; // 恰好取 p 個 1 long long val c base pre[p]; if (d 0) dp0[u] min(dp0[u], val); else if (d 1) dp1[u] min(dp1[u], val); else dpm1[u] min(dpm1[u], val); } } } int main() { scanf(%d, n); g.assign(n 1, {}); cost0.assign(n 1, 0); cost1.assign(n 1, 0); dp0.assign(n 1, INF); dp1.assign(n 1, INF); dpm1.assign(n 1, INF); sz.assign(n 1, 0); // 讀入每個點的兩種代價按題目實際格式調整 for (int i 1; i n; i) scanf(%lld %lld, cost0[i], cost1[i]); // 讀入 n-1 條邊 for (int i 1; i n; i) { int u, v; scanf(%d %d, u, v); g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); long long ans; if (n % 2 0) ans dp0[1]; else ans min(dp1[1], dpm1[1]); printf(%lld\n, ans); return 0; }幾個一定要盯緊的地方。第一遞歸DFS在n很大時可能爆棧穩(wěn)妥改迭代。第二讀入代價的格式一定要按題目來有的題給的是改色代價有的給的是初始色 花費別想當然。第三ans的選擇要按n的奇偶性來偶數(shù)n根節(jié)點差值必須為0奇數(shù)n取±1里較小的。第四INF別設太小4e18是個安全值但如果你用INF做加法記得防溢出我上面是先把base算好再加c沒直接加INF這點要留意。5. 對拍、卡常與賽時踩坑記錄5.1 幾個寫反就全錯的細節(jié)這題有幾處特別容易寫反或者漏掉。首先是w的符號定成顏色0時w1還是-1這取決于你delta的定義。我前面定義delta是顏色0的數(shù)量減去顏色1的數(shù)量所以定成0貢獻1。如果你的定義反了那w、dp1、dpm1的語義全都要跟著翻極容易出bug。寫代碼前先在紙上把定義寫死別中途改。其次是增量數(shù)組存的是dp1[v]-dpm1[v]別寫成dpm1[v]-dp1[v]。如果你寫反了排序取最小的p個會選出完全相反的方案答案直接錯。驗證方法拿一個只有兩個節(jié)點的樹手算兩個葉子都是奇數(shù)子樹看看取1和取-1分別對應什么。再一個是p的范圍檢查。num d - w m必須落在[0, 2m]且為偶數(shù)。有些人只檢查了p≥0忘了p≤m結果數(shù)組越界或者取到錯誤的p。這個檢查是必須的不是可選的。最后是dp數(shù)組的初始化時機。我們是在節(jié)點u的所有子節(jié)點處理完之后才初始化dp0[u]等為INF的然后才枚舉顏色更新。如果你提前初始化又中途被覆蓋就會丟解。5.2 用暴力對拍驗證的正確姿勢這道題的約束比較特殊光靠樣例很難覆蓋所有情況。我推薦寫一個暴力版本對拍對每個節(jié)點把它最終顏色當成變量0或1枚舉所有2?種染色方案檢查是否滿足每個子樹差值不超過1并計算代價取最小。n取到10左右就能跑雖然是指數(shù)級但對拍夠用了。對拍流程隨機生成n比如8到12、隨機生成樹結構、隨機生成代價然后跑你的正解和暴力比較結果。我大概跑了500組才敢放心提交的正解。這里有個經驗隨機生成樹的時候別總用隨機父節(jié)點那種那樣生成的樹太扁要混合生成鏈、菊花、隨機樹三種形態(tài)才能覆蓋到不同奇偶分布因為這道題對樹形結構非常敏感。5.3 特殊形態(tài)單鏈、菊花、n1單鏈是最容易暴露奇偶性bug的形態(tài)。一條長度為n的鏈每一層子樹的奇偶性交替變化你的狀態(tài)切換邏輯如果有一點問題單鏈上就會立刻出錯。建議手動構造n1、2、3、4的鏈逐個手算驗證。菊花圖根連著一堆葉子也值得測。此時根的子節(jié)點全是葉子每個都是奇數(shù)子樹m就等于葉子數(shù)轉移里恰好選p個取1的作用會被放大到極致能有效檢驗你的貪心選法。n1的情況更別漏此時根就是葉子沒有子節(jié)點m0delta只能是w±1答案就是min(cost0[1], cost1[1])。我見過有人在這種邊界上因為數(shù)組下標或者循環(huán)寫的直接RE。最后分享一個我自己踩過的坑優(yōu)化的時候我一度想省掉排序直接用所有負增量必選、正增量按需補結果發(fā)現(xiàn)當p小于負增量個數(shù)時也沒問題但當p大于負增量個數(shù)時邏輯就變得很繞容易越寫越亂。老老實實排序取前p個幾十行代碼清清楚楚何必跟自己較勁。這道完美樹繞了一大圈最后落在排序取最小的p個這么一個樸素的結論上反倒讓我覺得——約束越強、狀態(tài)越少題目反而越優(yōu)雅。