思路与算法

按直接上司建立有根树的孩子表，以1为根，用显式栈作DFS并记录访问顺序。每个节点的子树大小初始化为1，随后逆序处理DFS顺序，把当前节点的子树大小加到父亲。最后每个员工输出子树大小减1，即排除本人后的全部直接和间接下属。

正确性说明

DFS中父亲总在孩子之前记录，逆序后所有孩子都先于父亲处理。叶子的子树仅包含自己，初始值1正确。对一般节点，假设孩子的子树大小已正确，各孩子子树互不相交，合并它们并加上当前节点，恰是该节点的完整子树。因此归纳得到所有子树大小。直属及间接下属就是子树中除本人以外的员工，减1后正确。

复杂度

建立孩子表、初始化n个槽、DFS和逆序聚合各O(n)，总时间O(n)，额外空间O(n)，包括树、父亲、访问次序、显式栈和大小数组。n最大200000，使用显式栈避免深链导致递归栈溢出。单个下属计数最大n-1，int足够。

易错点

输出包含每个员工但不把本人算作下属。不能假设上司编号总比下属小，测试含重新编号的树。n=1输出0。最大深链和星形树分别检验深度、宽度，输入描述的是合法公司树。

参考代码（C++11）

#include <iostream>
#include <vector>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> child(n + 1);
    vector<int> parent(n + 1), order{1}, size(n + 1, 1);
    for (int i = 2; i <= n; ++i) {
        cin >> parent[i];
        child[parent[i]].push_back(i);
    }
    order.clear();
    vector<int> stack{1};
    while (!stack.empty()) {
        int u = stack.back();
        stack.pop_back();
        order.push_back(u);
        for (int v : child[u])
            stack.push_back(v);
    }
    for (int i = n - 1; i > 0; --i) {
        int u = order[i];
        size[parent[u]] += size[u];
    }
    for (int i = 1; i <= n; ++i) {
        if (i > 1)
            cout << ' ';
        cout << size[i] - 1;
    }
    cout << '\n';
}