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)/2n等于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_{ij} sz_i * sz_j这个公式看着简单但它有个隐藏条件不同黑点贡献的路径不会重复。因为一条合法路径只有一个黑点它就只会被那唯一的黑点统计一次路径上如果没有黑点不会被任何黑点统计路径上有两个或更多黑点也不可能被误统计。所以把每个黑点的贡献加起来就是最终答案。2.2 用“顺序累加”实现组合公式实现的时候不需要真的把所有 sz 存下来再两两相乘。因为两两相乘再加上单端点贡献可以用一个滚动变量做。维护一个变量 sum表示当前已经处理过的白色连通块大小之和。每遇到一个新的白色连通块大小为 sz先累加 sum * sz这对应“新块和之前所有块各选一个点”的双端点情况再累加 sz这对应“黑点本身作为端点终点落在新块里”的情况最后 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完全一致。这个顺序累加技巧在后面很多计数题里会出现能少开一个数组也少一层循环。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)/21e5 棵树的点对数大约是 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); } }调用前先判断当前节点是白色节点且没有被访问过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; 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; }我建议你自己实现一遍重点不是背代码而是体会“为什么这里只需要对邻居查id”。因为黑色节点本身是分隔点白块已经不会跨越任何黑点所以对于黑点u的某个白色邻居vcompId[v]对应的白块一定就是“从u出发经过v能到达的全部白点集合”这正是公式里的 sz。3.4 复杂度估算白块染色阶段每个白色节点只进入DFS一次黑色节点没有额外进入所以这一部分是O(n)。统计答案阶段对每个黑点遍历它的邻接边。树中所有节点的度之和等于2*(n-1)所以黑点遍历邻居的总次数是O(n)。虽然可能同一个白色节点同时连接多个黑点但统计时它只是作为邻居出现在不同黑点的邻接列表里访问次数等于它的度和所有边数同阶。整体复杂度就是O(n)空间复杂度O(n)。对于 n1e5 的数据范围运行时间非常宽裕递归栈深度最坏是链状树的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。当n1e5时这个值约为4.99995e9已经超过 int 能表示的约21亿。而且计数过程中sum * sz可能超过单条路径数更加要命。所以ans、sum、compSize全都得用 long long。比赛里因为这个吃罚时的人不少尤其是从int改long long时只改了ans忘了改sum也一样会溢出。顺手整理一个排查表现象原因解决办法样例过大数据WA白块DFS重复访问或者没有先预处理改成全局一次白块染色答案明显偏小int类型溢出ans、sum、compSize全部long long答案明显偏大双端点统计时重复算了自己与自己的组合检查sum更新顺序先算贡献再累加递归爆栈链状树导致递归深度过深平台栈够可忽略不安心可改栈式DFS颜色错位字符串和节点编号下标不一致读入后显式转成1-based5. 如果再变一变至少一个黑点和更多扩展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状态先把两种颜色对应成“墙”和“房间”。墙能切开房间房间的大小是基本单位。接下来无论题目怎么问你手里已经有房间了剩下的就是组合数学的事。