如果你刷过2020寒假算法基础集训营大概率对第一场的F题maki和tree有印象。这道题表面上是一个树上的路径计数问题背地里考的是“把关键节点当隔板”的建模能力。我第一次做的时候很快就写了一个树形DP样例一过就交结果WA到怀疑人生。后来把那棵树画在草稿纸上才意识到问题出在“方向”上一条合法路径的黑点是唯一的统计这个黑点时它周围的白色连通块一个都不能漏。这篇就按我的踩坑顺序把这道题的建模思路、两种实现和几个容易翻车的细节一次讲清楚。1. 读题别急着写代码路径里“恰好一个黑点”意味着什么1.1 题面到底在问什么给定一棵n个节点的树每个节点要么是黑色要么是白色问有多少条简单路径满足路径上恰好只有一个黑色节点。这里的简单路径就是树上两个端点之间唯一的那条链。换句话说路径上可以有任意多个白点但黑点数量必须精确等于1多一个少一个都不行。我当时的第一个反应是枚举所有点对判断每条路径上黑点数量。这个思路在n很小的时候可行但n一旦到1e5级别就直接废掉了。n个点的树一共有n*(n-1)/2条路径n1e5时是10^10量级哪怕每次判断路径只需要O(logn)时间也扛不住。所以必须在读题阶段就意识到这道题要的不是枚举而是利用树的结构做数学统计。1.2 暴力做法的复杂度门槛最直观的暴力有两条路。第一条是枚举点对后用LCA或者树剖维护路径上的黑点数单条路径查询可以做到O(logn)但点对数量是O(n^2)总复杂度还是O(n^2 logn)不可行。第二条是以每个点为起点做DFS一边走一边维护当前路径已经经过几个黑点计数条件满足的终点。这样相当于对每个起点做一次全树遍历总复杂度O(n^2)同样过不了十万级别的数据。看数据范围做题是竞赛里的基本习惯。碰到树上路径计数题如果n能到1e5那么目标复杂度基本锁定为O(n)或者O(n logn)。这就要求我们不能把每条路径单独拎出来看而是要把“大量路径”压缩成“少量结构”用组合数一次性算掉。maki和tree这个题恰好就把大结构藏在了颜色分布里。1.3 把条件翻译成树上的结构“恰好一个黑点”这个条件非常关键。整条路径上的黑点是唯一的这个唯一的黑点把路径天然分成左右两段左边从某个白点走到黑点右边从黑点走到另一个白点两段内部都只能出现白点。如果把这个黑点拿掉路径的两个端点一定落在两个不同的白色连通块里或者有一个端点就是黑点本身。所以路径的合法性不取决于具体端点的编号而取决于黑点周围的白色连通块长什么样。这一点就是整道题的突破口只要知道每个黑点周围每个方向的白色连通块大小就能通过组合数一次性算出这个黑点贡献多少条路径。题目名称里挂着的树形DP和树上DFS其实都是在为“拿到这些连通块大小”服务。2. 把黑点当隔板一个黑点贡献公式的完整推导2.1 删掉黑点之后树长什么样想象把所有黑点从树中删掉剩下的白点会被切分成若干个互不相连的连通块。任意两个白点如果属于同一个白块它们之间的路径完全由白点组成不经过任何黑点如果属于不同的白块那么它们之间的路径一定会路过至少一个黑点。这个“删黑点看白块”的视角把原来一团乱麻的树上路径问题变成了“块与块之间怎么组合”的问题。对某个黑点u来说真正有效的路径只有两类一类是一端是黑点u另一端落在相邻某个白块里另一类是两端分别落在u相邻的两个不同白块里路径自然穿过u。至于同一个白块内部两个点组成的路径根本不经过黑点u不可能对u产生贡献。2.2 一个黑点到底贡献多少条路径设黑点u周围有k个白色连通块大小分别为a1, a2, ..., ak。记S为所有白块大小之和Q为所有白块大小的平方和。那么黑点u的贡献分两部分算黑点u作为路径的端点。此时另一个端点可以在任意相邻白块中任选一共贡献S条路径。两个端点分别落在两个不同的白块中。从第i个白块选一个点从第j个白块选一个点路径一定经过黑点u贡献为sum(ij) ai * aj。这个值写成S和Q的形式就是(S^2 - Q) / 2。把两部分加起来一个黑点u的贡献就是S (S^2 - Q) / 2。这个公式就是整道题的答案核心所有实现代码本质上都在收集每个黑点周围的S和Q。2.3 等价写法与公式验证这个公式还有一个特别好的等价写法把黑点u本身也看作一个大小为1的“特殊白块”。所有块的总大小变成S1从这些块中任选两个点作为端点一共是C(S1, 2)种选法。再减去每个白块内部的C(ai, 2)剩下的正好是路径经过u且u是唯一黑点的路径数量。两个写法算出来完全一样可以用来交叉验证代码。用星形图感受一下一个黑点连着三个白色叶子三个白块大小都是1S3Q3贡献等于3(9-3)/26。这6条路径分别是黑点到三个叶子的3条以及三个叶子两两组合经过黑点的3条手数完全一致。我在推导完这个公式之后马上意识到后面的代码只需要做好一件事准确拿到每个黑点周围所有白块的大小。3. 最简单的实现DFS标白块再对每个黑点扫描3.1 第一次DFS给每个白色连通块编号因为树只有n个点和n-1条边我们可以对每个还没访问过的白点发起一次DFS把整个白色连通块完整遍历一遍统计出大小同时给块内所有点打上同一个blockId。这个DFS只经过白点遇到黑点就停下来所以天然把白块切得干干净净。实现时有两个细节值得注意。第一blockId数组可以同时充当vis标记省掉一个额外的布尔数组第二先用一个blockCnt给每个块编号在DFS过程中用curSize统计当前块的点数遍历结束后把curSize存进blockSize[blockCnt]。这样后面扫黑点时只要看到一个白点邻居就能直接通过blockId找到它所属的块再取出块大小。3.2 第二次遍历黑点收集周围白块大小对于每一个黑点u扫描一遍它的邻接表。只要邻居是白点它一定属于某个白块直接取blockSize[blockId[v]]就得到这个方向上的白块大小。把所有方向的白块大小收集起来代入S和Q的公式累加即可。这里有一个很重要的性质由于原图是一棵树同一个黑点的周围不可能出现两个邻居属于同一个白块。如果真的出现那两个邻居在白块内部有一条路径再加上它们各自连到黑点的两条边就会在树上构成环和树的定义矛盾。所以收集白块大小时完全不需要去重写起来非常省心。3.3 完整代码与复杂度这个写法结构很清晰代码量也小适合比赛里快速写完并用于对拍。完整C代码如下#include bits/stdc.h using namespace std; const int N 100005; vectorint e[N]; char col[N]; int n, blockCnt; int blockId[N], blockSize[N]; void dfsBlock(int u) { blockId[u] blockCnt; blockSize[blockCnt]; for (int v : e[u]) { if (col[v] W !blockId[v]) { dfsBlock(v); } } } int main() { scanf(%d, n); string s; cin s; for (int i 1; i n; i) col[i] s[i - 1]; for (int i 0; i n - 1; i) { int u, v; scanf(%d%d, u, v); e[u].push_back(v); e[v].push_back(u); } for (int i 1; i n; i) { if (col[i] W !blockId[i]) { blockCnt; dfsBlock(i); } } long long ans 0; for (int u 1; u n; u) { if (col[u] ! B) continue; long long S 0, sq 0; for (int v : e[u]) { if (col[v] W) { int sz blockSize[blockId[v]]; S sz; sq 1LL * sz * sz; } } ans S (S * S - sq) / 2; } printf(%lld\n, ans); return 0; }两次遍历加在一起每个白点在标块时被访问一次每条边在标块和扫邻接时各看了一次总复杂度O(n)空间复杂度O(n)。这个做法把问题拆成“无脑标块”加“无脑累加”几乎不可能写错是我做这道题时推荐的保底方案。4. 更“树形DP”的写法从子方向f数组到父方向ext数组4.1 定义f[u]时最容易踩的雷如果一上来就按“树形DP”的思路写很多人会定义f[u]为以u为根的子树中包含u且全为白色的连通块大小。这个定义很自然自底向上一次DFS就能算白点u的f[u]等于1加上所有白色子节点的f黑点u的f[u]直接等于0。但这个定义埋了一个巨大的坑f[u]永远只覆盖“子树方向”完全不包含“父方向”。根节点选在哪里直接影响你能看到哪些白块。比如链1W-2B-3W-4W以1为根做DFS黑点2能看到的只有右侧白块f[3]2左侧白块{1}完全不在统计范围内。于是黑点2的贡献被算成2正确答案却是5一下子就少了父方向贡献的3条路径。4.2 我当时翻车的完整排查过程我第一次提交WA之后第一反应是公式写错了。我把S和Q的推导重新算了两遍没发现问题又怀疑是白块去重没做改来改去还是错。最后把样例画在草稿纸上从黑点2出发把每个方向的白块都画出来才猛然发现漏掉的正是“父亲方向”那个白块。这个教训让我明白一个事在树上做路径统计只维护一个自底向上的DP数组往往不够。因为你以某个点为根之后每个节点天然被分成“子树方向”和“父方向”两类。如果问题里每个方向都可能贡献答案就必须要求你的DP状态能把两个方向都覆盖到。否则就会出现“样例全过提交全挂”的典型翻车。4.3 用自顶向下参数补齐父方向正确的树形DP写法需要两个阶段。第一阶段仍然自底向上算f[u]u为白点时f[u]等于1加上所有白色子节点的fu为黑点时f[u]等于0。第二阶段自顶向下维护一个ext数组ext[u]表示u的父方向连续白块大小。如果父节点是黑点或者u是根节点ext[u]就等于0。有了ext数组黑点u周围的白块集合就齐了ext[u]代表父方向所有白色子节点的f[v]代表各个子方向一个都不漏。白点u向下传递ext时要注意区分两种情况如果子节点v是白色那么v的父方向白块大小是ext[u] 1 sumWhite - f[v]如果v是黑色那么v的父方向白块大小是ext[u] 1 sumWhite。这里的sumWhite是u所有白色子节点的f值之和语义就是“从上面来的白块、u自己、以及u除了v这一支以外的所有白子树”。4.4 树形DP版本的完整代码这套版本比标块法多了一步ext的传递但全程只需要两次DFS没有额外的块编号数组逻辑上更贴近题目标签里的“树形DP”。完整代码如下#include bits/stdc.h using namespace std; const int N 100005; vectorint e[N]; char col[N]; int n; long long f[N], ext[N], ans; void dfs1(int u, int fa) { f[u] (col[u] W) ? 1 : 0; for (int v : e[u]) if (v ! fa) { dfs1(v, u); if (col[u] W) f[u] f[v]; } } void dfs2(int u, int fa) { if (col[u] B) { long long S ext[u], sq ext[u] * ext[u]; for (int v : e[u]) if (v ! fa col[v] W) { S f[v]; sq f[v] * f[v]; } ans S (S * S - sq) / 2; } if (col[u] B) { for (int v : e[u]) if (v ! fa) { ext[v] 0; dfs2(v, u); } } else { long long sumWhite 0; for (int v : e[u]) if (v ! fa col[v] W) sumWhite f[v]; for (int v : e[u]) if (v ! fa) { ext[v] ext[u] 1 sumWhite - ((col[v] W) ? f[v] : 0); dfs2(v, u); } } } int main() { scanf(%d, n); string s; cin s; for (int i 1; i n; i) col[i] s[i - 1]; for (int i 0; i n - 1; i) { int u, v; scanf(%d%d, u, v); e[u].push_back(v); e[v].push_back(u); } dfs1(1, 0); dfs2(1, 0); printf(%lld\n, ans); return 0; }我建议两个版本都亲手写一遍。标块法用来对拍确认答案树形DP版作为最终提交。实际对拍中两者结果完全一致但标块法在理解“父方向”这个问题上帮了我大忙。如果你只能记住一个版本我建议记住第二个因为它在“树上路径计数类”题目里更有普适性。5. 边界数据、long long和递归栈容易翻车的工程细节5.1 全黑、全白和单点树全黑树树里没有白块每个黑点周围的白块集合为空S和Q都是0答案自然是0。注意如果把题意理解成“至少一个黑点”全黑树会算出很大一个数字那说明题意理解偏了。全白树树里一个黑点都没有任意路径上的黑点数都是0不满足“恰好一个黑点”答案同样是0。这个结论很简单但全白树经常被用来卡不读题的人。单点树n1时树上不存在的路径按照“端点不同”的约定答案就是0。如果题面额外说明单点路径也算那就需要加上单个黑点的贡献。建议写代码之前先在注释里把所有路径约定固定下来避免思路跑偏。5.2 答案最大能到多大最坏情况下一个黑点连着所有白点白点形成n-1个大小为1的白块答案近似等于所有白点两两组合的路径数量达到n*(n-1)/2量级。n1e5时答案约5e9n2e5时约2e10早就溢出int了。所以S、sq、ans全部必须用long long。我见过不少人公式全对最后挂在int上。计算(S * S - sq) / 2的时候S本身是long longS*S在n2e5时会到4e10虽然64位撑得住但随手写int S就直接爆炸。这种错误样例很难发现因为小数据下答案根本不会超过int范围。5.3 递归深度与读入细节十万级别的树DFS递归深度可能到10万部分比赛环境的默认栈空间不够容易爆栈。比赛时优先用递归写法因为代码好写如果本地测试或者评测环境不给面子可以改成手写栈模拟。标块法改成迭代很简单维护一个显式栈反复访问节点即可树形DP的ext传递也能用栈模拟但代码会难看不少。读入字符串时下标从0开始建树时记得转成1-based。输入里可能出现孤立点单个节点也要正常处理不要因为它的邻接表为空就在某个循环里跳过。这些细节看起来微不足道实际对拍时最容易在这里来回折腾。6. 从maki和tree延伸出去的路径计数套路6.1 如果改成“至少一个黑点”这种变形在比赛里更常见。至少一个黑点的路径数等于所有路径数减去全白路径数。所有路径总数是n*(n-1)/2全白路径数就是把每个白块单独考虑块内任取两个点形成一条路径累加每个白块内部的C(sz, 2)。思路比“恰好一个”更直接甚至不需要对黑点做任何扫描。对比一下就能发现恰好一个黑点时我们围绕黑点做加法至少一个黑点时我们做减法。以后遇到类似题目先问自己一句这个条件适合加法拆解还是容斥减法往往决定了代码难度差一个量级。6.2 路径计数题的通用建模顺序这类题我现在形成了固定流程先把树画出来把所有的关键节点黑点、特殊点标出来然后删掉关键节点看剩下多少个普通连通块最后思考关键节点如何连接这些块用块的大小做组合。只要块的大小能算清楚路径计数一般就剩下公式代入问题。如果多个关键节点之间的影响很强比如要求路径上恰好经过k个关键节点就要多设计一层DP状态。核心思想还是那句关键节点当隔板普通连通块当基本单位。maki和tree把这个思想嵌入到了最简单的一层非常适合用来练手。6.3 一点个人经验收尾这个题我后来在别的地方又碰到过几次变体每一次都加深同一个教训路径计数题最怕的不是公式难而是统计漏方向。画图、对拍、把父方向单独拎出来验证这三件事能省掉大部分调题时间。如果你现在也被一道树上计数题卡住不妨先停下手里的代码把树画出来看看每个节点周围有哪些方向没有进到你定义的DP数组里。题目本身只是一个起点但它逼出来的“白色连通块加黑点贡献”的思路在很多树上路径题里都能复用。把这套建模吃透下次见到类似题就不会再对着样例发懵了。