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