公司下属

GitHub跳转原题关系图返回列表

员工关系是一棵以总经理为根的树,先从根 BFS 得到父先于子的访问序,再逆序把孩子子树大小累加给父亲,O(n) 得每人下属数。

OJ: roj

题目 ID: 2141

难度:普及-

标签:树DFSBFSpython

创建: 2026-10-08 07:52

更新: 2026-10-08 07:52

形式化题目

有 nn 个节点的有根树,根为 11。对每个 i∈[2,n]i \in [2, n] 给出 ii 的父亲 pip_i,其中 {p2,…,pn}\{p_2, \dots, p_n\} 由题目直接给出,不保证 pi<ip_i < i。对每个 1⩽i⩽n1 \leqslant i \leqslant n,求以 ii 为根的子树中除 ii 自身以外的节点数,即 size(i)−1\mathrm{size}(i) - 1。

正解

思路

朴素做法。 对每个节点 uu 各跑一遍 DFS/BFS 数它有多少后代,单次 O(n)O(n),总计 O(n2)O(n^2)。当树退化成一条长链 1→2→⋯→n1 \to 2 \to \dots \to n 时总步数约为 n2/2=2×1010n^2/2 = 2 \times 10^{10},在 1000 ms1000\text{ ms} 时限下必然超时。

瓶颈在哪。 节点 uu 的后代集合与它儿子 vv 的后代集合大量重叠,同一棵子树被反复遍历。

关键观察: 子树大小天然满足自底向上的递推

size(u)=1+∑v∈children(u)size(v)\mathrm{size}(u) = 1 + \sum_{v \in \mathrm{children}(u)} \mathrm{size}(v)

即每个节点的答案只依赖它直接孩子的答案。于是只要保证「孩子先于父亲被算完」这个顺序,每个节点就只需处理一次,总时间降到 O(n)O(n)。

怎么拿到这个顺序。 注意输入并不保证 pi<ip_i < i(第 10 组数据就是标签置换后的链,pip_i 经常大于 ii),所以不能简单地按编号从 nn 倒着扫。正确做法是建出邻接表后从根 11 做一次 BFS:

  • BFS 队列的一个天然性质是「入队时父亲一定先于孩子入队」,因此 BFS 序就是一组可行的拓扑序;
  • 反过来逆序遍历这个 BFS 序,就得到「孩子一定先于父亲」的处理顺序,可以放心地做 size[boss[u]] += size[u]。

这个写法还有两个好处:一是顺序来自显式队列,不写任何函数调用栈,n=2×105n = 2\times 10^5 的链状数据不会递归爆栈;二是递推只是数组加法,常数极小。

下面用一个 5 人的小例子(p2=1,p3=1,p4=2,p5=3p_2 = 1, p_3 = 1, p_4 = 2, p_5 = 3,即题面样例的结构)展示一次「BFS 序 + 逆序累加」的过程:

轮次 动作 数组变化
建树 1→{2,3}1 \to \{2, 3\},2→{4}2 \to \{4\},3→{5}3 \to \{5\} size = [_,1,1,1,1,1]
BFS 队列依次得到 order = [1, 2, 3, 4, 5]
逆序 1 处理 5,上司是 3 size[3] = 2
逆序 2 处理 4,上司是 2 size[2] = 2
逆序 3 处理 3,上司是 1 size[1] = 3
逆序 4 处理 2,上司是 1 size[1] = 5
输出 i=1..5i = 1..5 输出 size[i] - 1 4 1 1 0 0

与样例输出完全一致。注意员工 3 也是员工 1 的子树成员,它把自己算完的 size = 2 交给父亲 1 时,已经把下属 5 含在里面了——这正是「只上报一次、不重复遍历」的体现。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 07:52
# update_at: 2026-10-12 14:53

# 公司继承树:父亲孩子表示法 + BFS 序自底向上求子树大小
# 一个员工的三个字段聚合成 Node 对象:直接上司、全部直接下属、子树大小。
# 如何使用:
# 1. 读入员工 i 的上司 p:node[i].boss = p,node[p].child.append(i)
# 2. 从总经理 1 求 BFS 序(父亲先于孩子入队),逆序处理就是"孩子先算完"
# 3. 员工 i 的下属人数 = node[i].sz - 1(去掉本人)
# 注意:上司编号不保证小于本人编号,不能按编号倒着扫,必须用 BFS 序。

import sys
from collections.abc import Iterator


class Node:
    """员工 u:直接上司 + 全部直接下属 + 子树大小(含本人)。"""

    def __init__(self) -> None:
        self.boss = 0               # 直接上司编号,总经理 1 的上司记为 0
        self.child: list[int] = []  # 全部直接下属编号
        self.sz = 1                 # 以 u 为根的子树大小(含本人)


node: list[Node] = []  # node[u]:员工 u


def init(n: int) -> None:
    """造出 0..n 共 n+1 个员工,子树大小都先算作 1(只有自己)。"""
    global node
    node = [Node() for _ in range(n + 1)]


def build_order(n: int) -> list[int]:
    """从总经理 1 出发求 BFS 序:入队时父亲一定先于孩子,可以当拓扑序用。"""
    order = [1]
    for u in order:      # 边遍历边追加,等价于 BFS 队列,根一定在最前
        order += node[u].child
    return order


def calc_subtree_size(n: int) -> None:
    """逆着 BFS 序自底向上累加:孩子一定先算完,再把自己整棵子树报给上司。"""
    order = build_order(n)
    for u in reversed(order[1:]):  # 跳过根:根没有上司可上报
        node[node[u].boss].sz += node[u].sz


def solve() -> None:
    tokens = sys.stdin.buffer.read().split()
    if not tokens:  # 空输入保护
        return

    data: Iterator[int] = iter(map(int, tokens))
    n = next(data)

    init(n)
    for i in range(2, n + 1):
        p = next(data)
        node[i].boss = p
        node[p].child.append(i)  # 建边:上司 -> 直接下属

    calc_subtree_size(n)
    print(' '.join(str(node[i].sz - 1) for i in range(1, n + 1)))  # 下属人数 = 子树大小 - 1


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 07:52
 * update_at: 2026-10-12 14:56
 */
// main.cpp:父亲孩子表示法建公司继承树,BFS 序自底向上累加子树大小,每人输出 sz-1。
//
// 员工的三个字段聚合成 struct:直接上司、全部直接下属、子树大小。
// 上司编号不保证小于本人编号,不能按编号倒着扫;必须先从根 1 求 BFS 序
// (父亲一定先于孩子入队),再逆序累加,孩子就一定先算完。
// 子树大小最大是 n = 2*10^5,用 int 足够,不必上 ll。

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

const int maxn = 200005; // 题面 n <= 2*10^5,按上界开

struct Node {
    int boss;          // 直接上司编号,总经理 1 的上司记为 0
    vector<int> child; // 全部直接下属编号
    int sz;            // 以 u 为根的子树大小(含本人),最大 n,int 足够
};

Node node[maxn];  // node[u]:员工 u
int order[maxn];  // BFS 序:父亲一定排在孩子之前
int order_cnt;    // BFS 序里的员工个数,order[0..order_cnt-1]
ll n;             // 员工数量

// 读入:员工 2..n 各报一个直接上司,同时登记到上司的下属表里
void read_input() {
    cin >> n;
    for (ll i = 2; i <= n; i++) {
        cin >> node[i].boss;
        node[node[i].boss].child.push_back(i); // 建边:上司 -> 直接下属
    }
}

// 从总经理 1 出发求 BFS 序:入队时父亲一定先于孩子,可以当拓扑序用
void build_order() {
    int head = 0, tail = 0;
    order[tail++] = 1;
    while (head < tail) {
        int u = order[head++];
        for (size_t i = 0; i < node[u].child.size(); i++) {
            order[tail++] = node[u].child[i];
        }
    }
    order_cnt = tail;
}

// 逆着 BFS 序自底向上累加:孩子先算完,再把自己整棵子树的大小报给上司
void calc_subtree_size() {
    build_order();
    for (ll i = 1; i <= n; i++) {
        node[i].sz = 1; // 先假设每人只有自己
    }
    for (int i = order_cnt - 1; i >= 0; i--) {
        int u = order[i];
        if (u != 1) { // 根没有上司可上报
            node[node[u].boss].sz += node[u].sz;
        }
    }
}

void solve() {
    read_input();
    calc_subtree_size();

    // 员工 u 的下属人数 = 子树大小 - 1(去掉本人)
    for (ll i = 1; i <= n; i++) {
        if (i > 1) {
            cout << ' ';
        }
        cout << node[i].sz - 1;
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}

复杂度

建树读入 n−1n-1 条边为 O(n)O(n);BFS 与逆序累加各遍历每个节点一次,为 O(n)O(n);输出 nn 个数也为 O(n)O(n)。总时间 O(n)O(n),空间 O(n)O(n)(邻接表 n−1n-1 条边 + 三个长度 nn 的数组)。n=2×105n = 2 \times 10^5 时内存仅几 MB,远低于 512 MB512\text{ MB} 限制;CPython 实测最坏点(n=2×105n = 2\times10^5 的置换标签链)也在 0.3 s0.3\text{ s} 量级。

总结

本题是「树上子树大小」的模板题。两个要点:一是把「下属人数」翻译成 size(u)−1\mathrm{size}(u) - 1,把 O(n2)O(n^2) 的逐点搜索换成自底向上的一次累加;二是不要假设输入满足 pi<ip_i < i,用 BFS(或迭代 DFS)显式建出「父先于子」的顺序,既兼容任意标签顺序,又避开了递归深度限制。

main.py 用的是 for u in order 边遍历边追加的写法——Python 的 list 迭代器会在追加元素时继续读到新元素,效果与队列完全相同。若换成递归 DFS,在 2×1052\times 10^5 的长链上必须 sys.setrecursionlimit,本解法直接回避了这个问题。

说明:本题素材由仓库内的生成脚本(data.py)现造,题面为网络重建版本(一本通 2141 同题),出题意图与官方原题可能存在细微差异;data/ 覆盖了 n=1n = 1、n=2n = 2、纯链、完全二叉树、星形、随机树与标签置换链等结构。