信息学奥赛一本通的题解目录里P2141这道题经常被初学者翻出来问题名就叫“公司下属”。它的难点不在代码量而在于你有没有建立“树”的直觉公司里的层级关系可以抽象成一棵家族树每个人直接管理的是一群儿子节点而他名下的所有下属就是这棵子树上除自己以外的所有节点。这篇文章想把P2141从读题到AC的完整路径拆开先讲清楚为什么它是树再讲递归如何自然地数清下属人数最后给出能直接用的C代码和我的踩坑记录。如果你正在跟《信息学奥赛一本通》的目录刷题或者刚学到递归和树遍历这篇应当能帮你少走不少弯路。1. 题目到底在考什么读懂“公司下属”的关键1.1 题面故事与数据结构抽象我刚开始做P2141的时候第一反应是“这题怎么这么绕”又是公司又是下属好像是管理学题目。把故事剥掉以后其实就是给你n个点每个点都有一个上级有的点没有上级然后让你数一数每个点管辖多少个下级。这里“下级”是包含间接下级的比如A是B的上级B是C的上级那么A名下要有B和C两个人不能只数B。如果题目给的是“每个人的直接上级编号”那么从上级连一条边到下级就会得到一棵以总经理为根、从根指向叶子的树如果输入里出现了多个没有上级的人那这棵树会退化成森林。很多人第一眼会觉得“上级”和“下属”是两种关系但代码里只需要存一种从上级指向下级的邻接表用来递归统计。为什么不用存“我是谁的下级”这种反向关系因为统计下属数需要向下扩展也就是子节点列表。如果只存父节点你也能做但每次都要从根重新走非常麻烦正向邻接表维护children一次DFS就能拿到所有答案。1.2 为什么选树而不是图这个问题其实很关键。公司里的管理关系如果画成图你可能会担心一个员工被两个上级管或者出现A管B、B管C、C又管A的循环。但题面既然叫“直接上级”通常就隐含了每个非根节点只有一个上级因此不会出现环也不会出现“多父亲”。这种结构就是标准的树。树最大的好处是从根到任意节点的路径唯一每个节点只被处理一次就能得出正确结果不需要像图一样用visited数组防重复。反过来如果题目改成“同事协作网络”两个人之间可以互相认识那就是无向图要统计某个人的所有人际关系就得BFS/DFS加标记防止重复访问。P2141考的是最基础的树所以不要把它当图题去写。类比一下公司层级像文件夹目录一个文件夹只能属于一个父文件夹但一个文件夹下可以有多个子文件夹不可能出现“A文件夹既在B下面又在C下面”的情况。树模型就是这种结构。1.3 数据范围暗示的方向信息学竞赛题看到n的范围就能判断该用什么算法。假设n只有20你随便写甚至可以每个节点都从头沿着上级往上数。但一本通的题往往会把n给到10^5甚至更大此时如果对每个员工都做一次DFS最坏情况下O(n^2)会超时。正确的姿势是只遍历一次树在递归返回时顺带把子树大小传上来这样每个点、每条边只访问一次总复杂度O(n)。这也是P2141真正的考察点别满足于“能算出来”要算得快。很多题解里会告诉你“后序遍历”其实本质就是一次DFS把答案都算好。2. 核心思路与递归原理2.1 递推公式是怎么来的假设f[u]表示u这个员工一共管理多少个下属包括直接下级以及间接下属但不包括他自己。看一下u的直接下级集合children[u]任取其中一个直接下级vv的下面还有f[v]个下属而v自己也要算到u的下属里。所以v对u的贡献是f[v]1。把每个直接下级加起来就得到核心公式f[u] sum( f[v] 1 ) 其中 v 是 u 的直接下级如果u是叶子节点children[u]为空f[u]显然等于0。这个公式是整个P2141的题眼。为什么“1”这么重要很多新手容易算漏。例如公司只有两层层级老板A下属B。A的下属应该是1不是0计算时B的f[B]是0但还要把B本人加上因此需要01。如果漏掉这个1统计结果全部变成“只有间接下属没有直接下属”。我刷题时第一次AC失败就栽在这里。记忆技巧数人数的时候每个直接下级都要“一个算一个”他不一定还有下级但他自己肯定算一个。2.2 后序遍历为什么刚好适用递归函数的写法最重要的不是先访问还是后访问而是答案的合并时机。在P2141里要算u的下属数必须先知道每个v的下属数所以应该先递归处理子节点等子节点返回了f[v]再回头给u做加法。这种“先孩子后父亲”的顺序就是后序遍历。如果你反过来先给u累加一个大概的数再递归到v里面去父节点的值已经定型后面v的真实结果根本传不回来只能再写二次循环才能修正反而麻烦。用生活场景解释你让每个部门经理先把各自部门的人数报上来你心里先不着急汇总等所有经理都报告完了你在办公室统一加总。这就是后序。如果经理还没报数你就先把“大概人数”写到报表上后面必然要改来改去数据难以一致。代码上后序遍历的递归实现非常直观int dfs(int u) { int ans 0; for (int v : child[u]) { ans dfs(v) 1; } return ans; }这段代码已经能算出答案。很多题解会额外用一个数组f把每个u的结果存起来方便最后输出而不是只返回根的结果。你可以把函数改造成int dfs(int u) { int cnt 0; for (int v : child[u]) { cnt dfs(v) 1; } f[u] cnt; return cnt; }这样一次递归下来f数组里就是每个节点对应的下属总数。2.3 一次递归vs多次递归的复杂度对比假设有n100000的链式结构总经理管经理经理管组长组长管员工……如果对每个点单独向下遍历来统计链尾的节点访问1次上一级访问2次再上一级访问3次总访问次数约n(n1)/21e5的规模下就是50亿次级别显然跑不动。而一次后序遍历每条边只被走一次每个点只进入函数一次总的递归调用次数正好是n复杂度O(n)。这也是为什么P2141虽然是入门递归题却依然有信息学竞赛的味道你需要从“能不能算出来”提升到“能不能高效算出来”。一旦把树的遍历次数降下来后面所有树形DP题都是同一个思路。3. 完整实现与踩坑记录3.1 邻接表建树与C代码实现先写一个可以直接抄的C17版本。读入方式按最常见的“n个员工员工编号1..n老板编号用0表示没有上级”处理。如果题面给的是“第一行n第二行n个数第i个数表示i的上级编号”代码就是下面这样#include bits/stdc.h using namespace std; const int MAXN 100010; vectorint child[MAXN]; int f[MAXN]; int dfs(int u) { int cnt 0; for (int v : child[u]) { cnt dfs(v) 1; } f[u] cnt; return cnt; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint father(n 1); int root 0; for (int i 1; i n; i) { cin father[i]; if (father[i] 0) { root i; } else { child[father[i]].push_back(i); } } if (root ! 0) dfs(root); for (int i 1; i n; i) { cout f[i] \n; } return 0; }这个写法有几个细节。一是root的确定不能默认从1开始因为经理可能是任何编号甚至输入顺序是乱的。二是我用vector存孩子遍历时非常自然如果你为了追求性能后面可以改链式前向星。三是输出顺序题目如果要求按编号顺序输出每个人下属数那就for 1到n如果要求只输出某个人的答案就把f[目标]拿出来单独输出。不同版本的一本通OJ对输出格式可能略有差异看清题目再动手。3.2 小样例手推验证光有公式容易想当然我拿一个非常小的例子手推一遍。假设n7上级编号数组如下员工编号直属上级10213142526373树长这样1下面有2和32下面有4和53下面有6和7。叶子节点4、5、6、7没有下级所以f[4]f[5]f[6]f[7]0。节点2的直接下级是4和5贡献是f[4]11f[5]11加起来等于2。节点3同理等于2。节点1的直接下级是2和3贡献是f[2]13f[3]13所以f[1]6。最终f数组是[6,2,2,0,0,0,0]。这个结果很有意义总经理1确实管着其余6个人2管4和5两个人3管6和7两个人。如果你算出来的总经理不是6说明递归里加法或者1漏了。我建议你在本地编译器跑完这个样例再交题不要直接拿个大数据盲试。递归题的逻辑如果在小样例上都不对大数据只能更乱。3.3 输入输出的几个容易踩的坑第一个坑上级编号可能是自己。如果孩子列表里出现了father[i]i说明数据造错了或者你读取方向理解反。真遇到这种情况要回看题面可能是“第i个数字表示i的直属下级”而不是“上级”。方向反了会导致邻接表建出来是反的甚至出现自环。第二个坑多个根。题目如果没说“总经理只有一个”就可能出现好几棵互不关联的树比如两个部门各自独立汇报。上面代码只处理一个root遇到森林会漏。解决办法是先找出所有father[i]0的节点分别dfs。第三个坑输入顺序。有的题目先读边数m再读m条“u v”表示u是v的上级有的题目直接给出数组。这些版本只是建表方式不同核心DFS完全一样。4. 常见问题与排查技巧4.1 递归爆栈与“栈溢出”怎么办如果n到了10^5而且树退化成一条链递归深度就会达到10^5。有些OJ系统给程序栈空间比较小DFS深度一大就报“段错误”或“Runtime Error”本地却正常。遇到这种情况第一反应不要怀疑算法大概率是递归爆栈。解决办法有三个一是改成迭代版本用显式栈模拟后序遍历二是用编译器参数扩栈但OJ上不现实三是把递归改成递推按从深层到根层的顺序处理。我一直推荐第一种因为显式栈可控且不依赖环境。迭代后序遍历可以这样写先按“根-孩子”顺序压栈得到一个先序序列再把序列反转就相当于后序。代码如下vectorint order; stackint st; st.push(root); while (!st.empty()) { int u st.top(); st.pop(); order.push_back(u); for (int v : child[u]) { st.push(v); } } reverse(order.begin(), order.end()); for (int u : order) { int cnt 0; for (int v : child[u]) { cnt f[v] 1; } f[u] cnt; }为什么要反转先序序列是“父在前子在后面”反转后父节点一定会排在它的所有孩子之后满足后序“孩子算完再算父亲”的要求。这一步处理之后再大的链也不怕。4.2 森林、多组数据与“根不是1”的坑还有一类WA是“只dfs了一次根但前面明明有多棵树”。我在做一本通时经常有题目不给“n个点是一棵树”的保证只给n条上下级关系。如果里面有两个人都没有上级就必须把每个根都遍历到。否则没被访问到的树输出的f全为0答案自然错。处理方式很简单找根后for一遍for (int i 1; i n; i) { if (father[i] 0) dfs(i); }如果根是0编号题目用0表示空编号要小心数组越界建议把员工编号都加1处理。多组数据的题目每组都要清空child数组和f数组vector用clear()普通数组用memset。如果忘记清空上一组残留的数据会让答案莫名其妙大起来这种问题Debug时最头疼。4.3 变量类型、答案溢出与快读下属总人数最大是n-1如果n给到2^31级别int可能溢出。信息学竞赛里一般n不超过10^5或10^6int足够但保险起见可以把f数组和dfs的返回值都设成long long反正内存吃得下。另一个建议是养成加“快读”的习惯。上面代码用了ios::sync_with_stdio(false)和cin.tie(nullptr)这已经能让cin和scanf速度接近如果题目输入特别大可以手写getchar快读。但P2141这种题用关同步的cin足够不需要过度优化。重点是输出别用endl改用\n否则大量刷新缓冲区会拖慢很多倍尤其是输出n行答案时。5. 一道题背后的算法地图从一本通到实际应用5.1 从“数下属”到子树大小与树形DP你如果只把P2141当一道会了递归就行的题那可以出门了。但我想多说一句这道题背后是“子树大小”这个更通用的概念。把f[u]换成“子树的总节点数”即f[u]1就变成了经典的DFS统计子树规模很多树形DP的第一步都要先做这个预处理。比如求一棵树的重心需要知道每个节点的子树大小求树的直径需要从叶子向上累加链长求公司里一个部门的渗透力需要把下属人数按层级加权求和。这些题都是同一个模板后序遍历 向上返回子树信息。所以建议把P2141吃透不要背代码而是把递推关系讲给自己听每个直接下级贡献“他这个人他管的人”。会了这个再看“树上背包”“树的直径”就不会觉得突兀。5.2 工程场景里的递归统计du命令、组织权限树的启示递归统计下属不只存在于竞赛题里。你在Linux里执行du -sh系统就是递归统计一个目录下所有子目录和文件大小之和权限系统里计算一个部门包含多少子部门也是同一棵“上级-下级”树。甚至公司做组织架构图每个管理者的管理半径本质上就是P2141的变体。差别只是竞赛题里节点是员工编号工程里节点是数据库记录竞赛题用递归/栈工程里还要考虑循环引用和数据一致性。不过核心思想没有变树结构适合用后序遍历自底向上汇总这个技巧放在哪里都管用。5.3 再往后可以刷什么题如果你刷完P2141还想巩固推荐几类题一是“子树大小”相关的裸题比如求每个节点的子节点数量二是“树的深度/高度”从上往下传层数与本题的后序遍历形成对照三是“树的直径”要两次DFS或者后序更新最大链能让你看到子树返回值怎么组合四是“树的重心”需要同时统计子树规模和拆掉某个点后剩余部分的最大值。在一本通里这些题通常排在P2141后面的进阶章节。把这些题连起来练你对树的直觉会提高得很快。回到P2141本身它虽然只是“数下属”但能把这一步想明白后面很多内容都能触类旁通。最后聊点我自己的体会。刷信息学奥赛一本通这种题集很多人容易陷入“代码抄一抄过掉就完事”的状态尤其是P2141这种看起来简单的小题。但题目小不等于价值小我第一次独立写这个递推时也加错了位置把1写在括号外结果总经理下属数少了好几个。后来我养成一个习惯每道树上题都先画一棵小树手动跑一遍递推公式再允许自己写代码。这个习惯帮我省了很多Debug时间。如果你正在卡P2141不妨也试试先不要看题解自己画一棵5个节点的公司树把f值一个个标出来再对照代码输出。这样做一遍比你复制十份题解都记得牢。这也是我从“数下属”这题里真正学到的本事。