【题目描述】

【输入】

【输出】

【输入样例】

5
1 1 2 3

【输出样例】

4 1 1 0 0

【提示】

1. 题目分析

问题抽象：

公司的层级结构在数据结构中天然对应着一棵有根树。

• 节点：员工（1 号员工为根节点）。

• 边：直接上司到下属的管理关系（形成从上到下的有向边）。

• 目标：求出每个人在公司里的下属总人数。转化为图论语言，就是求“以当前节点为根的子树的大小（节点总数）减去 1（减去自己）”。

2. 思考过程

拿到这道题，我们应该经历以下思考路径：

1. 如何存储关系？

   数据量，如果用二维矩阵存图肯定爆内存（O(N^2)）。由于是稀疏图（树的边数是N-1），我们需要用邻接表存储。为了追求极致的时间和空间效率，我们选择链式前向星（数组模拟邻接表）。

2. 是有向边还是无向边？

   题目明确给出了“直接上司”的关系，即数据是单向传递的（上司 下属）。所以我们只需要建单向边，这样简化了后续的遍历操作（不需要像无向树那样传father参数来防止死循环）。

3. 如何计算人数？

   一个人的下属总数，等于他所有直接下属的团队人数之和。这是一种典型的“自底向上”的汇报模式，完美契合 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. 易错点总结

1. 链式前向星的初始化：h 数组存的是头指针，必须全部初始化为 -1（使用 memset(h, -1, sizeof(h))），否则遍历时找不到终止条件，会陷入死循环或越界。

2. I/O速度瓶颈：数据规模达到 20 万，如果使用原始的 cin/cout，在时间限制较紧（如 1.0s）的判题机上极易因为输入输出过慢而TLE（超时）。建议在 main 函数开头加上解除同步流的代码 ios::sync_with_stdio(false); cin.tie(0);。

3. 树的遍历方向：虽然是无环图，但如果自作聪明建了双向边（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;
}