2020牛客寒假算法基础集训营1的F题，名字叫maki和tree，题目标签写得很直白：树形DP、树上DFS。但这道题当年卡住不少人的地方不在代码，而在“到底该数什么”。它给出一棵节点染成黑白两色的树，要求统计满足特定条件的简单路径数量，核心套路是先切断所有黑点、把白色连通块大小算出来，再对每个黑点做组合合并。这个模型在后续很多树上路径计数题里都能复用，尤其是树形DP入门阶段，非常适合拿来反复咀嚼。如果你是刚开始刷树上问题、或者已经会基础DFS但面对“路径计数”没有手感，这篇文章就把从题意到推导再到完整代码的每一步都拆给你看。

1. 题目在讲什么：先看懂要数的东西

1.1 题意还原

maki和tree这道题，题面可以简化成一句话：给一棵有n个节点的树，每个节点被涂成黑色或白色，问有多少条简单路径满足“路径上恰好出现一个黑色节点”。

这里有几个词要抠清楚。

第一，“简单路径”指的是树上两点之间唯一的那条路径，不重复经过某个点或边。因为树没有环，所以任意两个点u和v之间都只有一条简单路径，计数时一般默认u < v，避免把一条路径正反数两遍。

第二，“恰好出现一个黑色节点”意味着路径两端点的颜色组合有三种可能：黑色到白色、白色到白色、以及白色到黑色。黑色到黑色是不会被数进去的，因为那样路径上至少有两个黑色节点。还要注意路径长度至少为1，所以必须是一条边以上的路径，单个节点不算。

第三，树的大小很关键。集训营的数据范围我记得是n最大到1e5，这意味着任何O(n^2)的枚举都会超时。也就是说，你不能真的去枚举所有点对，再沿着树跑一遍路径检查黑色节点数量。

1.2 直接暴力会怎样

很多刚接触树上计数的人第一反应是：枚举所有点对，用LCA或者直接DFS求路径，统计路径上黑色节点个数。复杂度大概是这样：

• 点对数量是 n*(n-1)/2，n等于1e5时是 5e9 级别；
• 每条路径如果要沿着邻接表走一遍，又得花 O(路径长度) 的时间；
• 就算用LCA优化，5e9 的枚举量本身就已经超时了。

所以这题真正的难点不是“怎么判断一条路径合不合法”，而是“能不能不一条条路径数，直接通过组合方式算出答案”。

树上的路径计数题，大部分都能从两个角度切入：要么按路径的某个特殊点分类，要么按连通块做容斥。maki和tree很适合“按黑色节点分类”这条路，因为合法的路径上恰好有一个黑点，这就等于说每个合法路径都有一个独一无二的黑点作为“身份证”。

1.3 一个必须先想明白的转化

如果一条路径上恰好有一个黑色点，比如黑色的节点x，那么这条路径一定满足：

• x在路径上；
• 路径除x以外全是白色节点；
• 整条路径上没有第二个黑点。

把黑点想象成“隔离墙”，把白点想象成“可连通的区域”。一棵树里所有黑点一旦被拿掉，剩下的白色节点会被切成若干个互不相连的白色连通块。任何一条合法路径，要么端点就是黑点本身，另一端落在某个白色连通块里；要么两个端点分别落在两个不同的白色连通块里，路径中间只有一个黑点。这个转化是整个解题思路的地基。

2. 核心解题思路：拆黑点、数白块

2.1 每个黑点独立计数

有了上面的转化，计数就可以按黑点逐个来做。对任意一个黑点u，假设与u相邻的白色连通块一共有k个，它们的大小分别是 sz1, sz2, ..., szk。

先看一个端点就是u的情况。路径形如 u -> 某个白色点，那么终点可以在任何一个与u相邻的白色连通块里。第一块给 u 提供 sz1 种选择，第二块提供 sz2 种选择，所有块加起来一共是 sum(sz_i) 种。这些路径都满足“恰好一个黑点”，因为从u出发走到白块内部，途中不会遇到其他黑点。

再看两个端点都是白色的情况。两个白色点不能落在同一个白色连通块里，因为如果它们落在同一个块里，把它们连起来的路径根本不会经过u，也就没有黑点。所以必须从两个不同的白色连通块各选一个点。假设选了第i块和第j块，方案数是 sz_i * sz_j。对所有 i < j 累加，就得到两个端点都是白色的合法路径数量。

所以，对于一个黑点u，它能贡献的合法路径数是：

sum_i sz_i + sum_{i<j} sz_i * sz_j

这个公式看着简单，但它有个隐藏条件：不同黑点贡献的路径不会重复。因为一条合法路径只有一个黑点，它就只会被那唯一的黑点统计一次；路径上如果没有黑点，不会被任何黑点统计；路径上有两个或更多黑点，也不可能被误统计。所以把每个黑点的贡献加起来就是最终答案。

2.2 用“顺序累加”实现组合公式

实现的时候不需要真的把所有 sz 存下来再两两相乘。因为两两相乘再加上单端点贡献，可以用一个滚动变量做。

维护一个变量 sum，表示当前已经处理过的白色连通块大小之和。每遇到一个新的白色连通块，大小为 sz：

• 先累加 sum * sz，这对应“新块和之前所有块各选一个点”的双端点情况；
• 再累加 sz，这对应“黑点本身作为端点，终点落在新块里”的情况；
• 最后 sum += sz，把这个新块并入已处理集合。

举个例子：一个黑点周围有三个白块，大小分别是 2、3、4。处理顺序任意：

• 第一块：贡献 2，sum = 2；
• 第二块：贡献 2*3 + 3 = 9，sum = 5；
• 第三块：贡献 5*4 + 4 = 24，sum = 9；

总贡献 = 2 + 9 + 24 = 35。手算验证一下：单端点情况 2+3+4=9，双端点情况 23 + 24 + 3*4 = 6+8+12=26，合计35，完全一致。

这个顺序累加技巧在后面很多计数题里会出现，能少开一个数组，也少一层循环。

2.3 题目真正需要的子问题

既然每个黑点要知道“相邻白色连通块大小”，那么问题就归结为：预处理出所有白色连通块的大小，并且能快速查到某个白色节点属于哪个白块、白块有多大。

这个子问题用一次树上DFS就能解决。从某个未访问的白色节点出发，只沿着白色节点走，就能走出一个完整的白色连通块。遍历时给块内所有白色节点打上同一个编号，同时统计大小。

因为黑色节点不会被访问，所以每个白块都被黑色节点“包围”。你可以把白色连通块理解为被黑点切出来的白色岛屿。我习惯把这种预处理叫做“白块染色”。染色完成后，每个白点记录了它所属的块id，每个id对应一个块大小。

这样处理的好处是：每个白色节点只被访问一次，复杂度是O(n)，不存在重复计算。后面统计答案时，对于每个黑点，只需要看一看它邻居中白色节点所属的白块大小，然后套组合公式。

这里有一个容易想歪的地方：黑点u周围的白色邻居可能属于同一个白块吗？不可能。如果两个白色邻居属于同一个白块，说明它们之间存在一条不经过u的白色路径，再加上u的这条边，就形成了一个环，和树的结构矛盾。所以每个黑点周围出现的白块id天然互不相同，计数时不会重复。

3. 树上DFS + 树形DP完整实现

3.1 存储与预处理

这题实现起来不复杂，但有几个细节建议一开始就做好：

• 颜色字符串读入后转成数组，字符 'W' 表示白色，'B' 表示黑色；
• 邻接表存边，注意是无向边，要加两次；
• 白块编号用 vector 存储块大小，块ID就从 vector 的索引走；
• 开 long long 存答案，答案量级最大能到 n*(n-1)/2，1e5 棵树的点对数大约是 5e9，int 肯定装不下。

白块染色的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); } }

调用前先判断当前节点是白色节点且没有被访问过：

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时走回头路。递归的时候遇到黑色节点直接跳过，所以整个白块永远不会跨过黑点。

3.2 统计答案的循环

白块大小处理完之后，再扫一遍所有黑点就行：

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";

这段代码非常短，但每个变量都值得说清楚。sum表示当前黑点u已经处理过的白色邻居所属白块大小之和。第一次遇到白块时，sum = 0，所以只加sz，也就是所有以黑点u为端点、终点落在当前白块的路径。第二次遇到白块时，sum已经有值，sum * sz就把“当前白块”和“之前所有白块”的双端点路径全部算进来。之后 sum 累加，继续处理下一个白块。

有的题解会在统计时额外处理“黑点自成一个集合”，然后让两个端点都来自不同集合。上面的写法其实已经隐式包含这个逻辑：黑点自身可以看成大小等于1的集合，只是我们把它放到公式里的方式不太一样。直接按“单端点 + 双端点”拆开，不容易漏，也不容易重复。

3.3 完整可运行代码

把上面几段拼起来，就是一个能在O(n)时间内跑完的完整代码：

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int n; vector<int> g[MAXN]; vector<char> color; bool vis[MAXN]; int compId[MAXN]; vector<long 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; }

我建议你自己实现一遍，重点不是背代码，而是体会“为什么这里只需要对邻居查id”。因为黑色节点本身是分隔点，白块已经不会跨越任何黑点，所以对于黑点u的某个白色邻居v，compId[v]对应的白块一定就是“从u出发经过v能到达的全部白点集合”，这正是公式里的 sz。

3.4 复杂度估算

白块染色阶段，每个白色节点只进入DFS一次，黑色节点没有额外进入，所以这一部分是O(n)。

统计答案阶段，对每个黑点遍历它的邻接边。树中所有节点的度之和等于2*(n-1)，所以黑点遍历邻居的总次数是O(n)。虽然可能同一个白色节点同时连接多个黑点，但统计时它只是作为邻居出现在不同黑点的邻接列表里，访问次数等于它的度，和所有边数同阶。

整体复杂度就是O(n)，空间复杂度O(n)。对于 n=1e5 的数据范围，运行时间非常宽裕，递归栈深度最坏是链状树的n，一般平台都能通过。

4. 常见问题与避坑记录

4.1 为什么不能用“每个黑点重新DFS一次”

这是我见过最多的错误写法：对每个黑点u，把它当成根，然后向每个白色邻居重新DFS一遍，求白块大小。从代码角度来说特别直观，但复杂度是灾难。

考虑一个极端情况：一条由10000个白色节点组成的长链，每个白色节点上额外挂一个黑色叶子节点。这样总节点数约20000，白色长链是同一个白块。对于每个黑色叶子，如果都从自身开始往白色邻居DFS，每次都会把整条白色长链访问一遍。黑色叶子数量乘以白链长度，复杂度直接变成O(n^2)级别，n稍微一涨就TLE。

正确做法就是提前把所有白块染色一次，统计的时候直接查块大小。这也是树形DP思想里常见的“空间换时间”：把重复计算变成预处理查询。

4.2 颜色数组和边读入的下标要一致

还有一次我看到同学把颜色字符串的0-based索引直接当成1-based节点号用，结果整棵树颜色全部错位。比较稳妥的写法是字符串先读进来，再用color[i] = s[i - 1]转成1-based数组。边读入时也统一从1到n。这类错位问题靠样例可能过不去，因为颜色错位不会导致逻辑崩溃，只会让答案完全不同。

4.3 黑点相邻会不会导致重复计数

如果树里有两个黑色节点直接相连，比如 b1 - b2 这条边，那么包含这条边的路径上至少有两个黑点，显然不能被统计。我们的算法会自动忽略它：处理b1时，只会看白色邻居；b2虽然是邻居，但不是白色，所以不会进入统计循环。处理b2也一样。所以黑黑相邻不会导致重复，也不用特判。

同理，如果一个黑色节点周围全是黑色邻居，它的贡献为0，完全不会影响答案。

4.4 忘记long long是这题最常见的低级失误

路径数答案最大是 n*(n-1)/2。当n=1e5时，这个值约为4.99995e9，已经超过 int 能表示的约21亿。而且计数过程中sum * sz可能超过单条路径数，更加要命。所以ans、sum、compSize全都得用 long long。比赛里因为这个吃罚时的人不少，尤其是从int改long long时只改了ans忘了改sum，也一样会溢出。

顺手整理一个排查表：

5. 如果再变一变：至少一个黑点和更多扩展

5.1 题目改成“至少一个黑点”

如果题意变成统计路径上至少有一个黑点的路径数量，比“恰好一个”更简单，因为思考方向可以反过来：总数减去全白路径。

总路径数是 n*(n-1)/2。全白路径指的是两个端点都属于同一个白色连通块、并且路径上没有任何黑点的路径。在每个白块内部，大小为 sz 的白块贡献的全白路径是 sz*(sz-1)/2。把所有白块的全白路径加起来，再用总路径数减去它，剩下的就是至少含一个黑点的路径数。

用我们预处理出来的compSize，这个变式只需要加一个循环就够了：

long long ans = 1LL * n * (n - 1) / 2; for (long long sz : compSize) { ans -= sz * (sz - 1) / 2; }

是不是感觉前面做的工作完全没浪费？同一套白块预处理，换一种统计思路就能适配另一个题目。

5.2 题目改成“恰好两个黑点”

“恰好两个黑点”会难一些，但也可以按黑点做组合。做法是枚举路径上两个端点所属的结构，或者枚举路径中间某个点，然后用辅助DP维护“从当前点出发经过一个黑点能到达的白色点数”。这里会用到类似背包合并的思路：每遇到一个白块就更新当前黑点累计值。整体框架还是树上DFS，只是公式从“一个黑点”升级成“两个黑点”。

这道题的思维路线一旦走通，很多树上路径计数题都会变成同一个套路：找到路径的“关键点”，把路径切分成分段，再由各侧大小组合相乘。maki和tree就是这个套路的极简入门版本。

5.3 和点分治、树形DP的关系

树上路径计数题，常见的三种武器是树形DP、点分治、以及这里用到的黑块分离。区别在于：

• 树形DP适合计数与某个固定根相关的结构，适合做子树合并；
• 点分治适合处理“任意两点路径”但树形结构又比较复杂的情况，通过重心分治把路径拆成跨重心；
• 黑块分离适合节点带有“特殊标记”的计数，直接把标记点当分隔，思路轻巧。

maki和tree表面上是树形DP题，实际操作更像“连通块染色 + 组合计数”。其实很多树形DP题的代码并不难，难的是把路径分类想明白。一旦分类想明白了，代码反而短得让人怀疑。

6. 最后一点个人体会

我直到现在做树上路径计数题，还会习惯性地先问自己一句：这条路径的“唯一身份标识”是什么。maki和tree里，恰好一个黑点就是身份标识。只要把合法路径按黑点分类，剩下的就是白块大小之间纯粹的数学组合。

如果打算用这道题做树形DP入门，我建议不要直接抄代码，而是先在纸上画一棵10个节点左右的小树，手动把所有黑点涂出来，再把白块圈出来。然后用文章里的公式手算一遍答案，再看代码，理解会深得多。这个“画图找规律”的习惯，比多刷十道类似题都有用。

再分享一个小技巧：遇到这种颜色分成两类、计数与路径有关的树上题，先别急着想DP状态，先把两种颜色对应成“墙”和“房间”。墙能切开房间，房间的大小是基本单位。接下来无论题目怎么问，你手里已经有房间了，剩下的就是组合数学的事。