計(jì)恰好一個(gè)黑點(diǎn)的路徑)
2020?？秃偎惴ɑA(chǔ)集訓(xùn)營1的F題名字叫maki和tree題目標(biāo)簽寫得很直白樹形DP、樹上DFS。但這道題當(dāng)年卡住不少人的地方不在代碼而在“到底該數(shù)什么”。它給出一棵節(jié)點(diǎn)染成黑白兩色的樹要求統(tǒng)計(jì)滿足特定條件的簡單路徑數(shù)量核心套路是先切斷所有黑點(diǎn)、把白色連通塊大小算出來再對(duì)每個(gè)黑點(diǎn)做組合合并。這個(gè)模型在后續(xù)很多樹上路徑計(jì)數(shù)題里都能復(fù)用尤其是樹形DP入門階段非常適合拿來反復(fù)咀嚼。如果你是剛開始刷樹上問題、或者已經(jīng)會(huì)基礎(chǔ)DFS但面對(duì)“路徑計(jì)數(shù)”沒有手感這篇文章就把從題意到推導(dǎo)再到完整代碼的每一步都拆給你看。1. 題目在講什么先看懂要數(shù)的東西1.1 題意還原maki和tree這道題題面可以簡化成一句話給一棵有n個(gè)節(jié)點(diǎn)的樹每個(gè)節(jié)點(diǎn)被涂成黑色或白色問有多少條簡單路徑滿足“路徑上恰好出現(xiàn)一個(gè)黑色節(jié)點(diǎn)”。這里有幾個(gè)詞要摳清楚。第一“簡單路徑”指的是樹上兩點(diǎn)之間唯一的那條路徑不重復(fù)經(jīng)過某個(gè)點(diǎn)或邊。因?yàn)闃錄]有環(huán)所以任意兩個(gè)點(diǎn)u和v之間都只有一條簡單路徑計(jì)數(shù)時(shí)一般默認(rèn)u v避免把一條路徑正反數(shù)兩遍。第二“恰好出現(xiàn)一個(gè)黑色節(jié)點(diǎn)”意味著路徑兩端點(diǎn)的顏色組合有三種可能黑色到白色、白色到白色、以及白色到黑色。黑色到黑色是不會(huì)被數(shù)進(jìn)去的因?yàn)槟菢勇窂缴现辽儆袃蓚€(gè)黑色節(jié)點(diǎn)。還要注意路徑長度至少為1所以必須是一條邊以上的路徑單個(gè)節(jié)點(diǎn)不算。第三樹的大小很關(guān)鍵。集訓(xùn)營的數(shù)據(jù)范圍我記得是n最大到1e5這意味著任何O(n^2)的枚舉都會(huì)超時(shí)。也就是說你不能真的去枚舉所有點(diǎn)對(duì)再沿著樹跑一遍路徑檢查黑色節(jié)點(diǎn)數(shù)量。1.2 直接暴力會(huì)怎樣很多剛接觸樹上計(jì)數(shù)的人第一反應(yīng)是枚舉所有點(diǎn)對(duì)用LCA或者直接DFS求路徑統(tǒng)計(jì)路徑上黑色節(jié)點(diǎn)個(gè)數(shù)。復(fù)雜度大概是這樣點(diǎn)對(duì)數(shù)量是 n*(n-1)/2n等于1e5時(shí)是 5e9 級(jí)別每條路徑如果要沿著鄰接表走一遍又得花 O(路徑長度) 的時(shí)間就算用LCA優(yōu)化5e9 的枚舉量本身就已經(jīng)超時(shí)了。所以這題真正的難點(diǎn)不是“怎么判斷一條路徑合不合法”而是“能不能不一條條路徑數(shù)直接通過組合方式算出答案”。樹上的路徑計(jì)數(shù)題大部分都能從兩個(gè)角度切入要么按路徑的某個(gè)特殊點(diǎn)分類要么按連通塊做容斥。maki和tree很適合“按黑色節(jié)點(diǎn)分類”這條路因?yàn)楹戏ǖ穆窂缴锨『糜幸粋€(gè)黑點(diǎn)這就等于說每個(gè)合法路徑都有一個(gè)獨(dú)一無二的黑點(diǎn)作為“身份證”。1.3 一個(gè)必須先想明白的轉(zhuǎn)化如果一條路徑上恰好有一個(gè)黑色點(diǎn)比如黑色的節(jié)點(diǎn)x那么這條路徑一定滿足x在路徑上路徑除x以外全是白色節(jié)點(diǎn)整條路徑上沒有第二個(gè)黑點(diǎn)。把黑點(diǎn)想象成“隔離墻”把白點(diǎn)想象成“可連通的區(qū)域”。一棵樹里所有黑點(diǎn)一旦被拿掉剩下的白色節(jié)點(diǎn)會(huì)被切成若干個(gè)互不相連的白色連通塊。任何一條合法路徑要么端點(diǎn)就是黑點(diǎn)本身另一端落在某個(gè)白色連通塊里要么兩個(gè)端點(diǎn)分別落在兩個(gè)不同的白色連通塊里路徑中間只有一個(gè)黑點(diǎn)。這個(gè)轉(zhuǎn)化是整個(gè)解題思路的地基。2. 核心解題思路拆黑點(diǎn)、數(shù)白塊2.1 每個(gè)黑點(diǎn)獨(dú)立計(jì)數(shù)有了上面的轉(zhuǎn)化計(jì)數(shù)就可以按黑點(diǎn)逐個(gè)來做。對(duì)任意一個(gè)黑點(diǎn)u假設(shè)與u相鄰的白色連通塊一共有k個(gè)它們的大小分別是 sz1, sz2, ..., szk。先看一個(gè)端點(diǎn)就是u的情況。路徑形如 u - 某個(gè)白色點(diǎn)那么終點(diǎn)可以在任何一個(gè)與u相鄰的白色連通塊里。第一塊給 u 提供 sz1 種選擇第二塊提供 sz2 種選擇所有塊加起來一共是 sum(sz_i) 種。這些路徑都滿足“恰好一個(gè)黑點(diǎn)”因?yàn)閺膗出發(fā)走到白塊內(nèi)部途中不會(huì)遇到其他黑點(diǎn)。再看兩個(gè)端點(diǎn)都是白色的情況。兩個(gè)白色點(diǎn)不能落在同一個(gè)白色連通塊里因?yàn)槿绻鼈兟湓谕粋€(gè)塊里把它們連起來的路徑根本不會(huì)經(jīng)過u也就沒有黑點(diǎn)。所以必須從兩個(gè)不同的白色連通塊各選一個(gè)點(diǎn)。假設(shè)選了第i塊和第j塊方案數(shù)是 sz_i * sz_j。對(duì)所有 i j 累加就得到兩個(gè)端點(diǎn)都是白色的合法路徑數(shù)量。所以對(duì)于一個(gè)黑點(diǎn)u它能貢獻(xiàn)的合法路徑數(shù)是sum_i sz_i sum_{ij} sz_i * sz_j這個(gè)公式看著簡單但它有個(gè)隱藏條件不同黑點(diǎn)貢獻(xiàn)的路徑不會(huì)重復(fù)。因?yàn)橐粭l合法路徑只有一個(gè)黑點(diǎn)它就只會(huì)被那唯一的黑點(diǎn)統(tǒng)計(jì)一次路徑上如果沒有黑點(diǎn)不會(huì)被任何黑點(diǎn)統(tǒng)計(jì)路徑上有兩個(gè)或更多黑點(diǎn)也不可能被誤統(tǒng)計(jì)。所以把每個(gè)黑點(diǎn)的貢獻(xiàn)加起來就是最終答案。2.2 用“順序累加”實(shí)現(xiàn)組合公式實(shí)現(xiàn)的時(shí)候不需要真的把所有 sz 存下來再兩兩相乘。因?yàn)閮蓛上喑嗽偌由蠁味它c(diǎn)貢獻(xiàn)可以用一個(gè)滾動(dòng)變量做。維護(hù)一個(gè)變量 sum表示當(dāng)前已經(jīng)處理過的白色連通塊大小之和。每遇到一個(gè)新的白色連通塊大小為 sz先累加 sum * sz這對(duì)應(yīng)“新塊和之前所有塊各選一個(gè)點(diǎn)”的雙端點(diǎn)情況再累加 sz這對(duì)應(yīng)“黑點(diǎn)本身作為端點(diǎn)終點(diǎn)落在新塊里”的情況最后 sum sz把這個(gè)新塊并入已處理集合。舉個(gè)例子一個(gè)黑點(diǎn)周圍有三個(gè)白塊大小分別是 2、3、4。處理順序任意第一塊貢獻(xiàn) 2sum 2第二塊貢獻(xiàn) 2*3 3 9sum 5第三塊貢獻(xiàn) 5*4 4 24sum 9總貢獻(xiàn) 2 9 24 35。手算驗(yàn)證一下單端點(diǎn)情況 2349雙端點(diǎn)情況 23 24 3*4 681226合計(jì)35完全一致。這個(gè)順序累加技巧在后面很多計(jì)數(shù)題里會(huì)出現(xiàn)能少開一個(gè)數(shù)組也少一層循環(huán)。2.3 題目真正需要的子問題既然每個(gè)黑點(diǎn)要知道“相鄰白色連通塊大小”那么問題就歸結(jié)為預(yù)處理出所有白色連通塊的大小并且能快速查到某個(gè)白色節(jié)點(diǎn)屬于哪個(gè)白塊、白塊有多大。這個(gè)子問題用一次樹上DFS就能解決。從某個(gè)未訪問的白色節(jié)點(diǎn)出發(fā)只沿著白色節(jié)點(diǎn)走就能走出一個(gè)完整的白色連通塊。遍歷時(shí)給塊內(nèi)所有白色節(jié)點(diǎn)打上同一個(gè)編號(hào)同時(shí)統(tǒng)計(jì)大小。因?yàn)楹谏?jié)點(diǎn)不會(huì)被訪問所以每個(gè)白塊都被黑色節(jié)點(diǎn)“包圍”。你可以把白色連通塊理解為被黑點(diǎn)切出來的白色島嶼。我習(xí)慣把這種預(yù)處理叫做“白塊染色”。染色完成后每個(gè)白點(diǎn)記錄了它所屬的塊id每個(gè)id對(duì)應(yīng)一個(gè)塊大小。這樣處理的好處是每個(gè)白色節(jié)點(diǎn)只被訪問一次復(fù)雜度是O(n)不存在重復(fù)計(jì)算。后面統(tǒng)計(jì)答案時(shí)對(duì)于每個(gè)黑點(diǎn)只需要看一看它鄰居中白色節(jié)點(diǎn)所屬的白塊大小然后套組合公式。這里有一個(gè)容易想歪的地方黑點(diǎn)u周圍的白色鄰居可能屬于同一個(gè)白塊嗎不可能。如果兩個(gè)白色鄰居屬于同一個(gè)白塊說明它們之間存在一條不經(jīng)過u的白色路徑再加上u的這條邊就形成了一個(gè)環(huán)和樹的結(jié)構(gòu)矛盾。所以每個(gè)黑點(diǎn)周圍出現(xiàn)的白塊id天然互不相同計(jì)數(shù)時(shí)不會(huì)重復(fù)。3. 樹上DFS 樹形DP完整實(shí)現(xiàn)3.1 存儲(chǔ)與預(yù)處理這題實(shí)現(xiàn)起來不復(fù)雜但有幾個(gè)細(xì)節(jié)建議一開始就做好顏色字符串讀入后轉(zhuǎn)成數(shù)組字符 W 表示白色B 表示黑色鄰接表存邊注意是無向邊要加兩次白塊編號(hào)用 vector 存儲(chǔ)塊大小塊ID就從 vector 的索引走開 long long 存答案答案量級(jí)最大能到 n*(n-1)/21e5 棵樹的點(diǎn)對(duì)數(shù)大約是 5e9int 肯定裝不下。白塊染色的DFS寫起來像這樣void dfsWhite(int u, int fa, int id, long long sz) { vis[u] true; compId[u] id; sz; for (int v : g[u]) { if (v fa) continue; if (color[v] B) continue; if (vis[v]) continue; dfsWhite(v, u, id, sz); } }調(diào)用前先判斷當(dāng)前節(jié)點(diǎn)是白色節(jié)點(diǎn)且沒有被訪問過for (int i 1; i n; i) { if (color[i] W !vis[i]) { int id compSize.size(); compSize.push_back(0); long long sz 0; dfsWhite(i, 0, id, sz); compSize[id] sz; } }這里把fa傳成0用來避免DFS時(shí)走回頭路。遞歸的時(shí)候遇到黑色節(jié)點(diǎn)直接跳過所以整個(gè)白塊永遠(yuǎn)不會(huì)跨過黑點(diǎn)。3.2 統(tǒng)計(jì)答案的循環(huán)白塊大小處理完之后再掃一遍所有黑點(diǎn)就行l(wèi)ong long ans 0; for (int u 1; u n; u) { if (color[u] ! B) continue; long long sum 0; for (int v : g[u]) { if (color[v] ! W) continue; int id compId[v]; long long sz compSize[id]; ans sz sum * sz; sum sz; } } cout ans \n;這段代碼非常短但每個(gè)變量都值得說清楚。sum表示當(dāng)前黑點(diǎn)u已經(jīng)處理過的白色鄰居所屬白塊大小之和。第一次遇到白塊時(shí)sum 0所以只加sz也就是所有以黑點(diǎn)u為端點(diǎn)、終點(diǎn)落在當(dāng)前白塊的路徑。第二次遇到白塊時(shí)sum已經(jīng)有值sum * sz就把“當(dāng)前白塊”和“之前所有白塊”的雙端點(diǎn)路徑全部算進(jìn)來。之后 sum 累加繼續(xù)處理下一個(gè)白塊。有的題解會(huì)在統(tǒng)計(jì)時(shí)額外處理“黑點(diǎn)自成一個(gè)集合”然后讓兩個(gè)端點(diǎn)都來自不同集合。上面的寫法其實(shí)已經(jīng)隱式包含這個(gè)邏輯黑點(diǎn)自身可以看成大小等于1的集合只是我們把它放到公式里的方式不太一樣。直接按“單端點(diǎn) 雙端點(diǎn)”拆開不容易漏也不容易重復(fù)。3.3 完整可運(yùn)行代碼把上面幾段拼起來就是一個(gè)能在O(n)時(shí)間內(nèi)跑完的完整代碼#include bits/stdc.h using namespace std; const int MAXN 100005; int n; vectorint g[MAXN]; vectorchar color; bool vis[MAXN]; int compId[MAXN]; vectorlong long compSize; void dfsWhite(int u, int fa, int id, long long sz) { vis[u] true; compId[u] id; sz; for (int v : g[u]) { if (v fa) continue; if (color[v] B) continue; if (vis[v]) continue; dfsWhite(v, u, id, sz); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; string s; cin s; color.resize(n 1); for (int i 1; i n; i) { color[i] s[i - 1]; } for (int i 1; i n; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } for (int i 1; i n; i) { if (color[i] W !vis[i]) { int id compSize.size(); compSize.push_back(0); long long sz 0; dfsWhite(i, 0, id, sz); compSize[id] sz; } } long long ans 0; for (int u 1; u n; u) { if (color[u] ! B) continue; long long sum 0; for (int v : g[u]) { if (color[v] ! W) continue; int id compId[v]; long long sz compSize[id]; ans sz sum * sz; sum sz; } } cout ans \n; return 0; }我建議你自己實(shí)現(xiàn)一遍重點(diǎn)不是背代碼而是體會(huì)“為什么這里只需要對(duì)鄰居查id”。因?yàn)楹谏?jié)點(diǎn)本身是分隔點(diǎn)白塊已經(jīng)不會(huì)跨越任何黑點(diǎn)所以對(duì)于黑點(diǎn)u的某個(gè)白色鄰居vcompId[v]對(duì)應(yīng)的白塊一定就是“從u出發(fā)經(jīng)過v能到達(dá)的全部白點(diǎn)集合”這正是公式里的 sz。3.4 復(fù)雜度估算白塊染色階段每個(gè)白色節(jié)點(diǎn)只進(jìn)入DFS一次黑色節(jié)點(diǎn)沒有額外進(jìn)入所以這一部分是O(n)。統(tǒng)計(jì)答案階段對(duì)每個(gè)黑點(diǎn)遍歷它的鄰接邊。樹中所有節(jié)點(diǎn)的度之和等于2*(n-1)所以黑點(diǎn)遍歷鄰居的總次數(shù)是O(n)。雖然可能同一個(gè)白色節(jié)點(diǎn)同時(shí)連接多個(gè)黑點(diǎn)但統(tǒng)計(jì)時(shí)它只是作為鄰居出現(xiàn)在不同黑點(diǎn)的鄰接列表里訪問次數(shù)等于它的度和所有邊數(shù)同階。整體復(fù)雜度就是O(n)空間復(fù)雜度O(n)。對(duì)于 n1e5 的數(shù)據(jù)范圍運(yùn)行時(shí)間非常寬裕遞歸棧深度最壞是鏈狀樹的n一般平臺(tái)都能通過。4. 常見問題與避坑記錄4.1 為什么不能用“每個(gè)黑點(diǎn)重新DFS一次”這是我見過最多的錯(cuò)誤寫法對(duì)每個(gè)黑點(diǎn)u把它當(dāng)成根然后向每個(gè)白色鄰居重新DFS一遍求白塊大小。從代碼角度來說特別直觀但復(fù)雜度是災(zāi)難?？紤]一個(gè)極端情況一條由10000個(gè)白色節(jié)點(diǎn)組成的長鏈每個(gè)白色節(jié)點(diǎn)上額外掛一個(gè)黑色葉子節(jié)點(diǎn)。這樣總節(jié)點(diǎn)數(shù)約20000白色長鏈?zhǔn)峭粋€(gè)白塊。對(duì)于每個(gè)黑色葉子如果都從自身開始往白色鄰居DFS每次都會(huì)把整條白色長鏈訪問一遍。黑色葉子數(shù)量乘以白鏈長度復(fù)雜度直接變成O(n^2)級(jí)別n稍微一漲就TLE。正確做法就是提前把所有白塊染色一次統(tǒng)計(jì)的時(shí)候直接查塊大小。這也是樹形DP思想里常見的“空間換時(shí)間”把重復(fù)計(jì)算變成預(yù)處理查詢。4.2 顏色數(shù)組和邊讀入的下標(biāo)要一致還有一次我看到同學(xué)把顏色字符串的0-based索引直接當(dāng)成1-based節(jié)點(diǎn)號(hào)用結(jié)果整棵樹顏色全部錯(cuò)位。比較穩(wěn)妥的寫法是字符串先讀進(jìn)來再用color[i] s[i - 1]轉(zhuǎn)成1-based數(shù)組。邊讀入時(shí)也統(tǒng)一從1到n。這類錯(cuò)位問題靠樣例可能過不去因?yàn)轭伾e(cuò)位不會(huì)導(dǎo)致邏輯崩潰只會(huì)讓答案完全不同。4.3 黑點(diǎn)相鄰會(huì)不會(huì)導(dǎo)致重復(fù)計(jì)數(shù)如果樹里有兩個(gè)黑色節(jié)點(diǎn)直接相連比如 b1 - b2 這條邊那么包含這條邊的路徑上至少有兩個(gè)黑點(diǎn)顯然不能被統(tǒng)計(jì)。我們的算法會(huì)自動(dòng)忽略它處理b1時(shí)只會(huì)看白色鄰居b2雖然是鄰居但不是白色所以不會(huì)進(jìn)入統(tǒng)計(jì)循環(huán)。處理b2也一樣。所以黑黑相鄰不會(huì)導(dǎo)致重復(fù)也不用特判。同理如果一個(gè)黑色節(jié)點(diǎn)周圍全是黑色鄰居它的貢獻(xiàn)為0完全不會(huì)影響答案。4.4 忘記long long是這題最常見的低級(jí)失誤路徑數(shù)答案最大是 n*(n-1)/2。當(dāng)n1e5時(shí)這個(gè)值約為4.99995e9已經(jīng)超過 int 能表示的約21億。而且計(jì)數(shù)過程中sum * sz可能超過單條路徑數(shù)更加要命。所以ans、sum、compSize全都得用 long long。比賽里因?yàn)檫@個(gè)吃罰時(shí)的人不少尤其是從int改long long時(shí)只改了ans忘了改sum也一樣會(huì)溢出。順手整理一個(gè)排查表現(xiàn)象原因解決辦法樣例過大數(shù)據(jù)WA白塊DFS重復(fù)訪問或者沒有先預(yù)處理改成全局一次白塊染色答案明顯偏小int類型溢出ans、sum、compSize全部long long答案明顯偏大雙端點(diǎn)統(tǒng)計(jì)時(shí)重復(fù)算了自己與自己的組合檢查sum更新順序先算貢獻(xiàn)再累加遞歸爆棧鏈狀樹導(dǎo)致遞歸深度過深平臺(tái)棧夠可忽略不安心可改棧式DFS顏色錯(cuò)位字符串和節(jié)點(diǎn)編號(hào)下標(biāo)不一致讀入后顯式轉(zhuǎn)成1-based5. 如果再變一變至少一個(gè)黑點(diǎn)和更多擴(kuò)展5.1 題目改成“至少一個(gè)黑點(diǎn)”如果題意變成統(tǒng)計(jì)路徑上至少有一個(gè)黑點(diǎn)的路徑數(shù)量比“恰好一個(gè)”更簡單因?yàn)樗伎挤较蚩梢苑催^來總數(shù)減去全白路徑。總路徑數(shù)是 n*(n-1)/2。全白路徑指的是兩個(gè)端點(diǎn)都屬于同一個(gè)白色連通塊、并且路徑上沒有任何黑點(diǎn)的路徑。在每個(gè)白塊內(nèi)部大小為 sz 的白塊貢獻(xiàn)的全白路徑是 sz*(sz-1)/2。把所有白塊的全白路徑加起來再用總路徑數(shù)減去它剩下的就是至少含一個(gè)黑點(diǎn)的路徑數(shù)。用我們預(yù)處理出來的compSize這個(gè)變式只需要加一個(gè)循環(huán)就夠了long long ans 1LL * n * (n - 1) / 2; for (long long sz : compSize) { ans - sz * (sz - 1) / 2; }是不是感覺前面做的工作完全沒浪費(fèi)同一套白塊預(yù)處理換一種統(tǒng)計(jì)思路就能適配另一個(gè)題目。5.2 題目改成“恰好兩個(gè)黑點(diǎn)”“恰好兩個(gè)黑點(diǎn)”會(huì)難一些但也可以按黑點(diǎn)做組合。做法是枚舉路徑上兩個(gè)端點(diǎn)所屬的結(jié)構(gòu)或者枚舉路徑中間某個(gè)點(diǎn)然后用輔助DP維護(hù)“從當(dāng)前點(diǎn)出發(fā)經(jīng)過一個(gè)黑點(diǎn)能到達(dá)的白色點(diǎn)數(shù)”。這里會(huì)用到類似背包合并的思路每遇到一個(gè)白塊就更新當(dāng)前黑點(diǎn)累計(jì)值。整體框架還是樹上DFS只是公式從“一個(gè)黑點(diǎn)”升級(jí)成“兩個(gè)黑點(diǎn)”。這道題的思維路線一旦走通很多樹上路徑計(jì)數(shù)題都會(huì)變成同一個(gè)套路找到路徑的“關(guān)鍵點(diǎn)”把路徑切分成分段再由各側(cè)大小組合相乘。maki和tree就是這個(gè)套路的極簡入門版本。5.3 和點(diǎn)分治、樹形DP的關(guān)系樹上路徑計(jì)數(shù)題常見的三種武器是樹形DP、點(diǎn)分治、以及這里用到的黑塊分離。區(qū)別在于樹形DP適合計(jì)數(shù)與某個(gè)固定根相關(guān)的結(jié)構(gòu)適合做子樹合并點(diǎn)分治適合處理“任意兩點(diǎn)路徑”但樹形結(jié)構(gòu)又比較復(fù)雜的情況通過重心分治把路徑拆成跨重心黑塊分離適合節(jié)點(diǎn)帶有“特殊標(biāo)記”的計(jì)數(shù)直接把標(biāo)記點(diǎn)當(dāng)分隔思路輕巧。maki和tree表面上是樹形DP題實(shí)際操作更像“連通塊染色 組合計(jì)數(shù)”。其實(shí)很多樹形DP題的代碼并不難難的是把路徑分類想明白。一旦分類想明白了代碼反而短得讓人懷疑。6. 最后一點(diǎn)個(gè)人體會(huì)我直到現(xiàn)在做樹上路徑計(jì)數(shù)題還會(huì)習(xí)慣性地先問自己一句這條路徑的“唯一身份標(biāo)識(shí)”是什么。maki和tree里恰好一個(gè)黑點(diǎn)就是身份標(biāo)識(shí)。只要把合法路徑按黑點(diǎn)分類剩下的就是白塊大小之間純粹的數(shù)學(xué)組合。如果打算用這道題做樹形DP入門我建議不要直接抄代碼而是先在紙上畫一棵10個(gè)節(jié)點(diǎn)左右的小樹手動(dòng)把所有黑點(diǎn)涂出來再把白塊圈出來。然后用文章里的公式手算一遍答案再看代碼理解會(huì)深得多。這個(gè)“畫圖找規(guī)律”的習(xí)慣比多刷十道類似題都有用。再分享一個(gè)小技巧遇到這種顏色分成兩類、計(jì)數(shù)與路徑有關(guān)的樹上題先別急著想DP狀態(tài)先把兩種顏色對(duì)應(yīng)成“墻”和“房間”。墻能切開房間房間的大小是基本單位。接下來無論題目怎么問你手里已經(jīng)有房間了剩下的就是組合數(shù)學(xué)的事。 maki和tree題解：樹形DP與DFS統(tǒng)計(jì)恰好一個(gè)黑點(diǎn)的路徑
2020?？秃偎惴ɑA(chǔ)集訓(xùn)營1的F題名字叫maki和tree題目標(biāo)簽寫得很直白樹形DP、樹上DFS。但這道題當(dāng)年卡住不少人的地方不在代碼而在“到底該數(shù)什么”。它給出一棵節(jié)點(diǎn)染成黑白兩色的樹要求統(tǒng)計(jì)滿足特定條件的簡單路徑數(shù)量核心套路是先切斷所有黑點(diǎn)、把白色連通塊大小算出來再對(duì)每個(gè)黑點(diǎn)做組合合并。這個(gè)模型在后續(xù)很多樹上路徑計(jì)數(shù)題里都能復(fù)用尤其是樹形DP入門階段非常適合拿來反復(fù)咀嚼。如果你是剛開始刷樹上問題、或者已經(jīng)會(huì)基礎(chǔ)DFS但面對(duì)“路徑計(jì)數(shù)”沒有手感這篇文章就把從題意到推導(dǎo)再到完整代碼的每一步都拆給你看。1. 題目在講什么先看懂要數(shù)的東西1.1 題意還原maki和tree這道題題面可以簡化成一句話給一棵有n個(gè)節(jié)點(diǎn)的樹每個(gè)節(jié)點(diǎn)被涂成黑色或白色問有多少條簡單路徑滿足“路徑上恰好出現(xiàn)一個(gè)黑色節(jié)點(diǎn)”。這里有幾個(gè)詞要摳清楚。第一“簡單路徑”指的是樹上兩點(diǎn)之間唯一的那條路徑不重復(fù)經(jīng)過某個(gè)點(diǎn)或邊。因?yàn)闃錄]有環(huán)所以任意兩個(gè)點(diǎn)u和v之間都只有一條簡單路徑計(jì)數(shù)時(shí)一般默認(rèn)u v避免把一條路徑正反數(shù)兩遍。第二“恰好出現(xiàn)一個(gè)黑色節(jié)點(diǎn)”意味著路徑兩端點(diǎn)的顏色組合有三種可能黑色到白色、白色到白色、以及白色到黑色。黑色到黑色是不會(huì)被數(shù)進(jìn)去的因?yàn)槟菢勇窂缴现辽儆袃蓚€(gè)黑色節(jié)點(diǎn)。還要注意路徑長度至少為1所以必須是一條邊以上的路徑單個(gè)節(jié)點(diǎn)不算。第三樹的大小很關(guān)鍵。集訓(xùn)營的數(shù)據(jù)范圍我記得是n最大到1e5這意味著任何O(n^2)的枚舉都會(huì)超時(shí)。也就是說你不能真的去枚舉所有點(diǎn)對(duì)再沿著樹跑一遍路徑檢查黑色節(jié)點(diǎn)數(shù)量。1.2 直接暴力會(huì)怎樣很多剛接觸樹上計(jì)數(shù)的人第一反應(yīng)是枚舉所有點(diǎn)對(duì)用LCA或者直接DFS求路徑統(tǒng)計(jì)路徑上黑色節(jié)點(diǎn)個(gè)數(shù)。復(fù)雜度大概是這樣點(diǎn)對(duì)數(shù)量是 n*(n-1)/2n等于1e5時(shí)是 5e9 級(jí)別每條路徑如果要沿著鄰接表走一遍又得花 O(路徑長度) 的時(shí)間就算用LCA優(yōu)化5e9 的枚舉量本身就已經(jīng)超時(shí)了。所以這題真正的難點(diǎn)不是“怎么判斷一條路徑合不合法”而是“能不能不一條條路徑數(shù)直接通過組合方式算出答案”。樹上的路徑計(jì)數(shù)題大部分都能從兩個(gè)角度切入要么按路徑的某個(gè)特殊點(diǎn)分類要么按連通塊做容斥。maki和tree很適合“按黑色節(jié)點(diǎn)分類”這條路因?yàn)楹戏ǖ穆窂缴锨『糜幸粋€(gè)黑點(diǎn)這就等于說每個(gè)合法路徑都有一個(gè)獨(dú)一無二的黑點(diǎn)作為“身份證”。1.3 一個(gè)必須先想明白的轉(zhuǎn)化如果一條路徑上恰好有一個(gè)黑色點(diǎn)比如黑色的節(jié)點(diǎn)x那么這條路徑一定滿足x在路徑上路徑除x以外全是白色節(jié)點(diǎn)整條路徑上沒有第二個(gè)黑點(diǎn)。把黑點(diǎn)想象成“隔離墻”把白點(diǎn)想象成“可連通的區(qū)域”。一棵樹里所有黑點(diǎn)一旦被拿掉剩下的白色節(jié)點(diǎn)會(huì)被切成若干個(gè)互不相連的白色連通塊。任何一條合法路徑要么端點(diǎn)就是黑點(diǎn)本身另一端落在某個(gè)白色連通塊里要么兩個(gè)端點(diǎn)分別落在兩個(gè)不同的白色連通塊里路徑中間只有一個(gè)黑點(diǎn)。這個(gè)轉(zhuǎn)化是整個(gè)解題思路的地基。2. 核心解題思路拆黑點(diǎn)、數(shù)白塊2.1 每個(gè)黑點(diǎn)獨(dú)立計(jì)數(shù)有了上面的轉(zhuǎn)化計(jì)數(shù)就可以按黑點(diǎn)逐個(gè)來做。對(duì)任意一個(gè)黑點(diǎn)u假設(shè)與u相鄰的白色連通塊一共有k個(gè)它們的大小分別是 sz1, sz2, ..., szk。先看一個(gè)端點(diǎn)就是u的情況。路徑形如 u - 某個(gè)白色點(diǎn)那么終點(diǎn)可以在任何一個(gè)與u相鄰的白色連通塊里。第一塊給 u 提供 sz1 種選擇第二塊提供 sz2 種選擇所有塊加起來一共是 sum(sz_i) 種。這些路徑都滿足“恰好一個(gè)黑點(diǎn)”因?yàn)閺膗出發(fā)走到白塊內(nèi)部途中不會(huì)遇到其他黑點(diǎn)。再看兩個(gè)端點(diǎn)都是白色的情況。兩個(gè)白色點(diǎn)不能落在同一個(gè)白色連通塊里因?yàn)槿绻鼈兟湓谕粋€(gè)塊里把它們連起來的路徑根本不會(huì)經(jīng)過u也就沒有黑點(diǎn)。所以必須從兩個(gè)不同的白色連通塊各選一個(gè)點(diǎn)。假設(shè)選了第i塊和第j塊方案數(shù)是 sz_i * sz_j。對(duì)所有 i j 累加就得到兩個(gè)端點(diǎn)都是白色的合法路徑數(shù)量。所以對(duì)于一個(gè)黑點(diǎn)u它能貢獻(xiàn)的合法路徑數(shù)是sum_i sz_i sum_{ij} sz_i * sz_j這個(gè)公式看著簡單但它有個(gè)隱藏條件不同黑點(diǎn)貢獻(xiàn)的路徑不會(huì)重復(fù)。因?yàn)橐粭l合法路徑只有一個(gè)黑點(diǎn)它就只會(huì)被那唯一的黑點(diǎn)統(tǒng)計(jì)一次路徑上如果沒有黑點(diǎn)不會(huì)被任何黑點(diǎn)統(tǒng)計(jì)路徑上有兩個(gè)或更多黑點(diǎn)也不可能被誤統(tǒng)計(jì)。所以把每個(gè)黑點(diǎn)的貢獻(xiàn)加起來就是最終答案。2.2 用“順序累加”實(shí)現(xiàn)組合公式實(shí)現(xiàn)的時(shí)候不需要真的把所有 sz 存下來再兩兩相乘。因?yàn)閮蓛上喑嗽偌由蠁味它c(diǎn)貢獻(xiàn)可以用一個(gè)滾動(dòng)變量做。維護(hù)一個(gè)變量 sum表示當(dāng)前已經(jīng)處理過的白色連通塊大小之和。每遇到一個(gè)新的白色連通塊大小為 sz先累加 sum * sz這對(duì)應(yīng)“新塊和之前所有塊各選一個(gè)點(diǎn)”的雙端點(diǎn)情況再累加 sz這對(duì)應(yīng)“黑點(diǎn)本身作為端點(diǎn)終點(diǎn)落在新塊里”的情況最后 sum sz把這個(gè)新塊并入已處理集合。舉個(gè)例子一個(gè)黑點(diǎn)周圍有三個(gè)白塊大小分別是 2、3、4。處理順序任意第一塊貢獻(xiàn) 2sum 2第二塊貢獻(xiàn) 2*3 3 9sum 5第三塊貢獻(xiàn) 5*4 4 24sum 9總貢獻(xiàn) 2 9 24 35。手算驗(yàn)證一下單端點(diǎn)情況 2349雙端點(diǎn)情況 23 24 3*4 681226合計(jì)35完全一致。這個(gè)順序累加技巧在后面很多計(jì)數(shù)題里會(huì)出現(xiàn)能少開一個(gè)數(shù)組也少一層循環(huán)。2.3 題目真正需要的子問題既然每個(gè)黑點(diǎn)要知道“相鄰白色連通塊大小”那么問題就歸結(jié)為預(yù)處理出所有白色連通塊的大小并且能快速查到某個(gè)白色節(jié)點(diǎn)屬于哪個(gè)白塊、白塊有多大。這個(gè)子問題用一次樹上DFS就能解決。從某個(gè)未訪問的白色節(jié)點(diǎn)出發(fā)只沿著白色節(jié)點(diǎn)走就能走出一個(gè)完整的白色連通塊。遍歷時(shí)給塊內(nèi)所有白色節(jié)點(diǎn)打上同一個(gè)編號(hào)同時(shí)統(tǒng)計(jì)大小。因?yàn)楹谏?jié)點(diǎn)不會(huì)被訪問所以每個(gè)白塊都被黑色節(jié)點(diǎn)“包圍”。你可以把白色連通塊理解為被黑點(diǎn)切出來的白色島嶼。我習(xí)慣把這種預(yù)處理叫做“白塊染色”。染色完成后每個(gè)白點(diǎn)記錄了它所屬的塊id每個(gè)id對(duì)應(yīng)一個(gè)塊大小。這樣處理的好處是每個(gè)白色節(jié)點(diǎn)只被訪問一次復(fù)雜度是O(n)不存在重復(fù)計(jì)算。后面統(tǒng)計(jì)答案時(shí)對(duì)于每個(gè)黑點(diǎn)只需要看一看它鄰居中白色節(jié)點(diǎn)所屬的白塊大小然后套組合公式。這里有一個(gè)容易想歪的地方黑點(diǎn)u周圍的白色鄰居可能屬于同一個(gè)白塊嗎不可能。如果兩個(gè)白色鄰居屬于同一個(gè)白塊說明它們之間存在一條不經(jīng)過u的白色路徑再加上u的這條邊就形成了一個(gè)環(huán)和樹的結(jié)構(gòu)矛盾。所以每個(gè)黑點(diǎn)周圍出現(xiàn)的白塊id天然互不相同計(jì)數(shù)時(shí)不會(huì)重復(fù)。3. 樹上DFS 樹形DP完整實(shí)現(xiàn)3.1 存儲(chǔ)與預(yù)處理這題實(shí)現(xiàn)起來不復(fù)雜但有幾個(gè)細(xì)節(jié)建議一開始就做好顏色字符串讀入后轉(zhuǎn)成數(shù)組字符 W 表示白色B 表示黑色鄰接表存邊注意是無向邊要加兩次白塊編號(hào)用 vector 存儲(chǔ)塊大小塊ID就從 vector 的索引走開 long long 存答案答案量級(jí)最大能到 n*(n-1)/21e5 棵樹的點(diǎn)對(duì)數(shù)大約是 5e9int 肯定裝不下。白塊染色的DFS寫起來像這樣void dfsWhite(int u, int fa, int id, long long sz) { vis[u] true; compId[u] id; sz; for (int v : g[u]) { if (v fa) continue; if (color[v] B) continue; if (vis[v]) continue; dfsWhite(v, u, id, sz); } }調(diào)用前先判斷當(dāng)前節(jié)點(diǎn)是白色節(jié)點(diǎn)且沒有被訪問過for (int i 1; i n; i) { if (color[i] W !vis[i]) { int id compSize.size(); compSize.push_back(0); long long sz 0; dfsWhite(i, 0, id, sz); compSize[id] sz; } }這里把fa傳成0用來避免DFS時(shí)走回頭路。遞歸的時(shí)候遇到黑色節(jié)點(diǎn)直接跳過所以整個(gè)白塊永遠(yuǎn)不會(huì)跨過黑點(diǎn)。3.2 統(tǒng)計(jì)答案的循環(huán)白塊大小處理完之后再掃一遍所有黑點(diǎn)就行l(wèi)ong long ans 0; for (int u 1; u n; u) { if (color[u] ! B) continue; long long sum 0; for (int v : g[u]) { if (color[v] ! W) continue; int id compId[v]; long long sz compSize[id]; ans sz sum * sz; sum sz; } } cout ans \n;這段代碼非常短但每個(gè)變量都值得說清楚。sum表示當(dāng)前黑點(diǎn)u已經(jīng)處理過的白色鄰居所屬白塊大小之和。第一次遇到白塊時(shí)sum 0所以只加sz也就是所有以黑點(diǎn)u為端點(diǎn)、終點(diǎn)落在當(dāng)前白塊的路徑。第二次遇到白塊時(shí)sum已經(jīng)有值sum * sz就把“當(dāng)前白塊”和“之前所有白塊”的雙端點(diǎn)路徑全部算進(jìn)來。之后 sum 累加繼續(xù)處理下一個(gè)白塊。有的題解會(huì)在統(tǒng)計(jì)時(shí)額外處理“黑點(diǎn)自成一個(gè)集合”然后讓兩個(gè)端點(diǎn)都來自不同集合。上面的寫法其實(shí)已經(jīng)隱式包含這個(gè)邏輯黑點(diǎn)自身可以看成大小等于1的集合只是我們把它放到公式里的方式不太一樣。直接按“單端點(diǎn) 雙端點(diǎn)”拆開不容易漏也不容易重復(fù)。3.3 完整可運(yùn)行代碼把上面幾段拼起來就是一個(gè)能在O(n)時(shí)間內(nèi)跑完的完整代碼#include bits/stdc.h using namespace std; const int MAXN 100005; int n; vectorint g[MAXN]; vectorchar color; bool vis[MAXN]; int compId[MAXN]; vectorlong long compSize; void dfsWhite(int u, int fa, int id, long long sz) { vis[u] true; compId[u] id; sz; for (int v : g[u]) { if (v fa) continue; if (color[v] B) continue; if (vis[v]) continue; dfsWhite(v, u, id, sz); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; string s; cin s; color.resize(n 1); for (int i 1; i n; i) { color[i] s[i - 1]; } for (int i 1; i n; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } for (int i 1; i n; i) { if (color[i] W !vis[i]) { int id compSize.size(); compSize.push_back(0); long long sz 0; dfsWhite(i, 0, id, sz); compSize[id] sz; } } long long ans 0; for (int u 1; u n; u) { if (color[u] ! B) continue; long long sum 0; for (int v : g[u]) { if (color[v] ! W) continue; int id compId[v]; long long sz compSize[id]; ans sz sum * sz; sum sz; } } cout ans \n; return 0; }我建議你自己實(shí)現(xiàn)一遍重點(diǎn)不是背代碼而是體會(huì)“為什么這里只需要對(duì)鄰居查id”。因?yàn)楹谏?jié)點(diǎn)本身是分隔點(diǎn)白塊已經(jīng)不會(huì)跨越任何黑點(diǎn)所以對(duì)于黑點(diǎn)u的某個(gè)白色鄰居vcompId[v]對(duì)應(yīng)的白塊一定就是“從u出發(fā)經(jīng)過v能到達(dá)的全部白點(diǎn)集合”這正是公式里的 sz。3.4 復(fù)雜度估算白塊染色階段每個(gè)白色節(jié)點(diǎn)只進(jìn)入DFS一次黑色節(jié)點(diǎn)沒有額外進(jìn)入所以這一部分是O(n)。統(tǒng)計(jì)答案階段對(duì)每個(gè)黑點(diǎn)遍歷它的鄰接邊。樹中所有節(jié)點(diǎn)的度之和等于2*(n-1)所以黑點(diǎn)遍歷鄰居的總次數(shù)是O(n)。雖然可能同一個(gè)白色節(jié)點(diǎn)同時(shí)連接多個(gè)黑點(diǎn)但統(tǒng)計(jì)時(shí)它只是作為鄰居出現(xiàn)在不同黑點(diǎn)的鄰接列表里訪問次數(shù)等于它的度和所有邊數(shù)同階。整體復(fù)雜度就是O(n)空間復(fù)雜度O(n)。對(duì)于 n1e5 的數(shù)據(jù)范圍運(yùn)行時(shí)間非常寬裕遞歸棧深度最壞是鏈狀樹的n一般平臺(tái)都能通過。4. 常見問題與避坑記錄4.1 為什么不能用“每個(gè)黑點(diǎn)重新DFS一次”這是我見過最多的錯(cuò)誤寫法對(duì)每個(gè)黑點(diǎn)u把它當(dāng)成根然后向每個(gè)白色鄰居重新DFS一遍求白塊大小。從代碼角度來說特別直觀但復(fù)雜度是災(zāi)難?？紤]一個(gè)極端情況一條由10000個(gè)白色節(jié)點(diǎn)組成的長鏈每個(gè)白色節(jié)點(diǎn)上額外掛一個(gè)黑色葉子節(jié)點(diǎn)。這樣總節(jié)點(diǎn)數(shù)約20000白色長鏈?zhǔn)峭粋€(gè)白塊。對(duì)于每個(gè)黑色葉子如果都從自身開始往白色鄰居DFS每次都會(huì)把整條白色長鏈訪問一遍。黑色葉子數(shù)量乘以白鏈長度復(fù)雜度直接變成O(n^2)級(jí)別n稍微一漲就TLE。正確做法就是提前把所有白塊染色一次統(tǒng)計(jì)的時(shí)候直接查塊大小。這也是樹形DP思想里常見的“空間換時(shí)間”把重復(fù)計(jì)算變成預(yù)處理查詢。4.2 顏色數(shù)組和邊讀入的下標(biāo)要一致還有一次我看到同學(xué)把顏色字符串的0-based索引直接當(dāng)成1-based節(jié)點(diǎn)號(hào)用結(jié)果整棵樹顏色全部錯(cuò)位。比較穩(wěn)妥的寫法是字符串先讀進(jìn)來再用color[i] s[i - 1]轉(zhuǎn)成1-based數(shù)組。邊讀入時(shí)也統(tǒng)一從1到n。這類錯(cuò)位問題靠樣例可能過不去因?yàn)轭伾e(cuò)位不會(huì)導(dǎo)致邏輯崩潰只會(huì)讓答案完全不同。4.3 黑點(diǎn)相鄰會(huì)不會(huì)導(dǎo)致重復(fù)計(jì)數(shù)如果樹里有兩個(gè)黑色節(jié)點(diǎn)直接相連比如 b1 - b2 這條邊那么包含這條邊的路徑上至少有兩個(gè)黑點(diǎn)顯然不能被統(tǒng)計(jì)。我們的算法會(huì)自動(dòng)忽略它處理b1時(shí)只會(huì)看白色鄰居b2雖然是鄰居但不是白色所以不會(huì)進(jìn)入統(tǒng)計(jì)循環(huán)。處理b2也一樣。所以黑黑相鄰不會(huì)導(dǎo)致重復(fù)也不用特判。同理如果一個(gè)黑色節(jié)點(diǎn)周圍全是黑色鄰居它的貢獻(xiàn)為0完全不會(huì)影響答案。4.4 忘記long long是這題最常見的低級(jí)失誤路徑數(shù)答案最大是 n*(n-1)/2。當(dāng)n1e5時(shí)這個(gè)值約為4.99995e9已經(jīng)超過 int 能表示的約21億。而且計(jì)數(shù)過程中sum * sz可能超過單條路徑數(shù)更加要命。所以ans、sum、compSize全都得用 long long。比賽里因?yàn)檫@個(gè)吃罰時(shí)的人不少尤其是從int改long long時(shí)只改了ans忘了改sum也一樣會(huì)溢出。順手整理一個(gè)排查表現(xiàn)象原因解決辦法樣例過大數(shù)據(jù)WA白塊DFS重復(fù)訪問或者沒有先預(yù)處理改成全局一次白塊染色答案明顯偏小int類型溢出ans、sum、compSize全部long long答案明顯偏大雙端點(diǎn)統(tǒng)計(jì)時(shí)重復(fù)算了自己與自己的組合檢查sum更新順序先算貢獻(xiàn)再累加遞歸爆棧鏈狀樹導(dǎo)致遞歸深度過深平臺(tái)棧夠可忽略不安心可改棧式DFS顏色錯(cuò)位字符串和節(jié)點(diǎn)編號(hào)下標(biāo)不一致讀入后顯式轉(zhuǎn)成1-based5. 如果再變一變至少一個(gè)黑點(diǎn)和更多擴(kuò)展5.1 題目改成“至少一個(gè)黑點(diǎn)”如果題意變成統(tǒng)計(jì)路徑上至少有一個(gè)黑點(diǎn)的路徑數(shù)量比“恰好一個(gè)”更簡單因?yàn)樗伎挤较蚩梢苑催^來總數(shù)減去全白路徑。總路徑數(shù)是 n*(n-1)/2。全白路徑指的是兩個(gè)端點(diǎn)都屬于同一個(gè)白色連通塊、并且路徑上沒有任何黑點(diǎn)的路徑。在每個(gè)白塊內(nèi)部大小為 sz 的白塊貢獻(xiàn)的全白路徑是 sz*(sz-1)/2。把所有白塊的全白路徑加起來再用總路徑數(shù)減去它剩下的就是至少含一個(gè)黑點(diǎn)的路徑數(shù)。用我們預(yù)處理出來的compSize這個(gè)變式只需要加一個(gè)循環(huán)就夠了long long ans 1LL * n * (n - 1) / 2; for (long long sz : compSize) { ans - sz * (sz - 1) / 2; }是不是感覺前面做的工作完全沒浪費(fèi)同一套白塊預(yù)處理換一種統(tǒng)計(jì)思路就能適配另一個(gè)題目。5.2 題目改成“恰好兩個(gè)黑點(diǎn)”“恰好兩個(gè)黑點(diǎn)”會(huì)難一些但也可以按黑點(diǎn)做組合。做法是枚舉路徑上兩個(gè)端點(diǎn)所屬的結(jié)構(gòu)或者枚舉路徑中間某個(gè)點(diǎn)然后用輔助DP維護(hù)“從當(dāng)前點(diǎn)出發(fā)經(jīng)過一個(gè)黑點(diǎn)能到達(dá)的白色點(diǎn)數(shù)”。這里會(huì)用到類似背包合并的思路每遇到一個(gè)白塊就更新當(dāng)前黑點(diǎn)累計(jì)值。整體框架還是樹上DFS只是公式從“一個(gè)黑點(diǎn)”升級(jí)成“兩個(gè)黑點(diǎn)”。這道題的思維路線一旦走通很多樹上路徑計(jì)數(shù)題都會(huì)變成同一個(gè)套路找到路徑的“關(guān)鍵點(diǎn)”把路徑切分成分段再由各側(cè)大小組合相乘。maki和tree就是這個(gè)套路的極簡入門版本。5.3 和點(diǎn)分治、樹形DP的關(guān)系樹上路徑計(jì)數(shù)題常見的三種武器是樹形DP、點(diǎn)分治、以及這里用到的黑塊分離。區(qū)別在于樹形DP適合計(jì)數(shù)與某個(gè)固定根相關(guān)的結(jié)構(gòu)適合做子樹合并點(diǎn)分治適合處理“任意兩點(diǎn)路徑”但樹形結(jié)構(gòu)又比較復(fù)雜的情況通過重心分治把路徑拆成跨重心黑塊分離適合節(jié)點(diǎn)帶有“特殊標(biāo)記”的計(jì)數(shù)直接把標(biāo)記點(diǎn)當(dāng)分隔思路輕巧。maki和tree表面上是樹形DP題實(shí)際操作更像“連通塊染色 組合計(jì)數(shù)”。其實(shí)很多樹形DP題的代碼并不難難的是把路徑分類想明白。一旦分類想明白了代碼反而短得讓人懷疑。6. 最后一點(diǎn)個(gè)人體會(huì)我直到現(xiàn)在做樹上路徑計(jì)數(shù)題還會(huì)習(xí)慣性地先問自己一句這條路徑的“唯一身份標(biāo)識(shí)”是什么。maki和tree里恰好一個(gè)黑點(diǎn)就是身份標(biāo)識(shí)。只要把合法路徑按黑點(diǎn)分類剩下的就是白塊大小之間純粹的數(shù)學(xué)組合。如果打算用這道題做樹形DP入門我建議不要直接抄代碼而是先在紙上畫一棵10個(gè)節(jié)點(diǎn)左右的小樹手動(dòng)把所有黑點(diǎn)涂出來再把白塊圈出來。然后用文章里的公式手算一遍答案再看代碼理解會(huì)深得多。這個(gè)“畫圖找規(guī)律”的習(xí)慣比多刷十道類似題都有用。再分享一個(gè)小技巧遇到這種顏色分成兩類、計(jì)數(shù)與路徑有關(guān)的樹上題先別急著想DP狀態(tài)先把兩種顏色對(duì)應(yīng)成“墻”和“房間”。墻能切開房間房間的大小是基本單位。接下來無論題目怎么問你手里已經(jīng)有房間了剩下的就是組合數(shù)學(xué)的事。