员工关系是一棵以总经理为根的树,先从根 BFS 得到父先于子的访问序,再逆序把孩子子树大小累加给父亲,O(n) 得每人下属数。
OJ: roj
题目 ID: 2141
难度:普及-
标签:树DFSBFSpython
创建: 2026-10-08 07:52
更新: 2026-10-08 07:52
形式化题目
有
正解
思路
朴素做法。 对每个节点
瓶颈在哪。 节点
关键观察: 子树大小天然满足自底向上的递推
即每个节点的答案只依赖它直接孩子的答案。于是只要保证「孩子先于父亲被算完」这个顺序,每个节点就只需处理一次,总时间降到
怎么拿到这个顺序。 注意输入并不保证
- BFS 队列的一个天然性质是「入队时父亲一定先于孩子入队」,因此 BFS 序就是一组可行的拓扑序;
- 反过来逆序遍历这个 BFS 序,就得到「孩子一定先于父亲」的处理顺序,可以放心地做
size[boss[u]] += size[u]。
这个写法还有两个好处:一是顺序来自显式队列,不写任何函数调用栈,
下面用一个 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 |
| 输出 | size[i] - 1 |
4 1 1 0 0 |
与样例输出完全一致。注意员工 3 也是员工 1 的子树成员,它把自己算完的 size = 2 交给父亲 1 时,已经把下属 5 含在里面了——这正是「只上报一次、不重复遍历」的体现。
代码
#!/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()/**
* 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;
}复杂度
建树读入
总结
本题是「树上子树大小」的模板题。两个要点:一是把「下属人数」翻译成
main.py 用的是 for u in order 边遍历边追加的写法——Python 的 list 迭代器会在追加元素时继续读到新元素,效果与队列完全相同。若换成递归 DFS,在 sys.setrecursionlimit,本解法直接回避了这个问题。
说明:本题素材由仓库内的生成脚本(
data.py)现造,题面为网络重建版本(一本通 2141 同题),出题意图与官方原题可能存在细微差异;data/覆盖了、 、纯链、完全二叉树、星形、随机树与标签置换链等结构。