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