公司下属（信息学奥赛一本通- P2141）
【题目描述】
根据公司的结构，你的任务是计算每位员工的下属人数。
【输入】
第一行输入一个整数n，表示员工的数量。员工的编号为1、2、…、n，其中员工1是公司的总经理。之后有n−1个整数：对于每个员工2、3、…、n，这些整数表示他们在公司中的直接上司。
【输出】
n个整数：对于每个员工1、2、…、n，输出其下属的人数。
【输入样例】
5 1 1 2 3【输出样例】
4 1 1 0 0【提示】
数据范围：
1≤n≤2⋅10^5
1. 题目分析
问题抽象：
公司的层级结构在数据结构中天然对应着一棵有根树。
节点：员工（1 号员工为根节点）。
边：直接上司到下属的管理关系（形成从上到下的有向边）。
目标：求出每个人在公司里的下属总人数。转化为图论语言，就是求“以当前节点为根的子树的大小（节点总数）减去 1（减去自己）”。
2. 思考过程
拿到这道题，我们应该经历以下思考路径：
如何存储关系？
数据量
，如果用二维矩阵存图肯定爆内存（O(N^2)）。由于是稀疏图（树的边数是N-1），我们需要用邻接表存储。为了追求极致的时间和空间效率，我们选择链式前向星（数组模拟邻接表）。
是有向边还是无向边？
题目明确给出了“直接上司”的关系，即数据是单向传递的（上司
下属）。所以我们只需要建单向边，这样简化了后续的遍历操作（不需要像无向树那样传
father参数来防止死循环）。如何计算人数？
一个人的下属总数，等于他所有直接下属的团队人数之和。这是一种典型的“自底向上”的汇报模式，完美契合DFS（深度优先搜索）的后序遍历思想。
3. 解题思路与算法设计
核心算法：树形 DFS (树形DP的基础)
状态定义：定义
sz[x]表示以节点x为根的子树的节点总数（包含x自己）。初始状态：对于任何一个节点，最开始它所在的子树只有它自己，所以
sz[x]=1。状态转移：遍历x的所有直接下属v，递归调用
dfs(v)算出v的子树大小。然后将结果汇报给上司：sz[x]+=sz[v]。最终答案：题目要求下属人数，不包含自己，所以节点x的答案就是
sz[x]-1。
4. 时空复杂度分析
时间复杂度：O(N)。由于这是一棵树，DFS 会精确地访问每个节点一次，并且遍历每条边一次。建图耗时O(N)，遍历耗时O(N)，总时间复杂度为线性的O(N)，对于
的数据量来说不到0.05秒即可跑完。
空间复杂度：O(N)。使用了
h,vtex,nxt三个数组存边（共约字节），加上
sz数组以及DFS的系统调用栈。总空间完全在限制之内。
5. 易错点总结
链式前向星的初始化：
h数组存的是头指针，必须全部初始化为-1（使用memset(h, -1, sizeof(h))），否则遍历时找不到终止条件，会陷入死循环或越界。I/O速度瓶颈：数据规模达到 20 万，如果使用原始的
cin/cout，在时间限制较紧（如 1.0s）的判题机上极易因为输入输出过慢而TLE（超时）。建议在main函数开头加上解除同步流的代码ios::sync_with_stdio(false); cin.tie(0);。树的遍历方向：虽然是无环图，但如果自作聪明建了双向边（
addedge(u, i)和addedge(i, u)），DFS 时如果不加father参数屏蔽回头路，瞬间就会因为无限递归导致MLE/RE（爆栈）。本题充分利用单向边特性，避开了这个问题。
6. 完整代码
#include <iostream> #include <cstring>//对应memset函数 using namespace std; int n; int h[200010];//存储每个节点的最后一条出边的索引 int vtex[200010];//存储边的终点 int nxt[200010];//存储同起点的上一条边的索引 int idx; //sz[i]代表i的子树团体内总共多少节点（包含i) int sz[200010]; void addedge(int u,int v){ vtex[idx]=v; nxt[idx]=h[u]; h[u]=idx++; } void dfs(int x){ sz[x]=1;//初始化只有自己一个 int p=h[x]; while(p!=-1){//遍历x所有下属 int v=vtex[p]; dfs(v);//递归到叶子节点，先让下属去统计自己的团队人数 sz[x]+=sz[v];//下属统计完后，给上司累加 p=nxt[p];//更新指针到下一个下属 } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n; //初始化头指针数组为空 memset(h,-1,sizeof(h)); //存图 for(int i=2;i<=n;i++){ int u; cin>>u; addedge(u,i); } dfs(1);//1是总经理 //每个人的下属团体总人数-1就是下属人数 for(int i=1;i<=n;i++) cout<<sz[i]-1<<" "; return 0; }