問題文
您是A公司的总裁。 A公司由N个组织组成,每个组织的编号从0开始。 它的编号为N - 1。 编号为 0 的组织是顶级组织。
组织之间存在父子关系,并且数字不为0N - 1每个组织都有一个上级组织。 可以有多个子组织。 此外,每个组织都与最高组织直接或间接相关。
您要求所有组织提交报告。 为了避免拥塞,请重复“当每个组织完成其子组织的报告时,它会添加自己的报告并将其传递给父组织。”的过程。 没有任何附属组织的组织立即将报告传递给上级组织。 一旦最高组织完成了其下属组织的报告,它就会添加自己的报告并提交给总统。
每个组织将提交一份报告。
对于每个组织,请创建一个程序来输出“该组织将提交给上级组织的报告数量”。 但是,对于高层组织,请输出向主席提交的报告数量。
示例程序
#include <bits/stdc++.h>
using namespace std;
// x番の組織が親組織に提出する枚数を返す
// childrenは組織の関係を表す2次元配列(参照渡し)
int count_report_num(vector<vector<int>> &children, int x) {
// (ここに追記して再帰関数を実装する)
}
// これ以降の行は変更しなくてよい
int main() {
int N;
cin >> N;
vector<int> p(N); // 各組織の親組織を示す配列
p.at(0) = -1; // 0番組織の親組織は存在しないので-1を入れておく
for (int i = 1; i < N; i++) {
cin >> p.at(i);
}
// 組織の関係から2次元配列を作る
vector<vector<int>> children(N); // ある組織の子組織の番号一覧
for (int i = 1; i < N; i++) {
int parent = p.at(i); // i番の親組織の番号
children.at(parent).push_back(i); // parentの子組織一覧にi番を追加
}
// 各組織について、答えを出力
for (int i = 0; i < N; i++) {
cout << count_report_num(children, i) << endl;
}
}
関数count_report_num的参数children是一个二维数组,
编号为
x的组织的子组织编号表的排列是
您可以通过children.at(x)获得它。
制約
- 1 \leq N \leq 50
- 0 \leq p_i < i (1 \leq i \leq N - 1)
入力
输入是从标准输入按以下格式给出的: 编号为
N
p_1 p_2 p_3 \ldots p_{N - 1}
p_i为i的组织的上级组织是
表示该组织是p_i。
请注意,组织编号 0 是顶级组织,没有父组织。
出力
ans_0
ans_1
ans_2
\vdots
ans_{N - 1}
从组织编号0开始, 关于组织编号i的回答 请为每一行输出ans_i。
Judge 还测试以下输入示例以外的情况。注意。
入力例1
6 0 0 1 1 4
出力例1
6 4 1 1 2 1
组织关系如下图所示。 (箭头从子组织指向父组织。)

数字旁边的蓝色数字是每个组织的答案。
入力例2
8 0 0 1 2 0 3 6
出力例2
8 4 2 3 1 1 2 1
组织关系如下图所示。 (箭头从子组织指向父组织。)

数字旁边的蓝色数字是每个组织的答案。
提示
点击打开提示
- 「組織x提交给上级组织' = 组织x的所有子组织 关于c从c收到的报告总数 + 1 从
- 「c收到的报告数量" = "c提交给上级组织”
- 对于没有任何附属组织的组织,该组织向上级组织提交的报告数量为 1。
通过执行以下操作
您可以处理编号为x的组织的子组织。
for (int c : children.at(x)) {
// (cについての処理)
}
这个问题是 该问题与2.05.再帰関数示例非常相似,因此也请参考该示例。
测试输入/输出
仅当您编写的程序没有成为 AC 并且您不知道原因时,请参阅此内容。
单击查看测试输入/输出
测试输入 1
20 0 1 1 3 0 0 1 3 5 9 6 8 8 8 0 4 7 12 13
测试输出 1
20 13 1 9 2 3 2 2 6 2 1 1 2 2 1 1 1 1 1 1
测试输入 2
30 0 1 0 1 0 3 1 2 8 6 1 3 0 4 2 3 0 14 16 13 5 2 16 14 19 2 7 2 26
测试输出 2
30 16 8 8 4 2 2 2 2 1 1 1 1 2 3 1 4 1 1 2 1 1 1 1 1 1 2 1 1 1
测试输入 3
50 0 0 0 2 3 1 6 3 4 0 9 5 2 12 7 13 14 1 3 14 2 10 17 7 8 1 15 11 19 29 26 20 7 18 10 24 19 2 19 29 29 9 21 42 0 19 24 44 26
测试输出 3
50 14 13 18 7 7 8 7 2 6 3 2 6 2 5 2 1 2 2 8 2 2 1 1 3 1 3 1 1 4 1 1 1 1 1 1 1 1 1 1 1 1 3 1 2 1 1 1 1 1
解答例
观看前请务必亲自尝试一下问题。
点击查看示例答案
#include <bits/stdc++.h>
using namespace std;
// x番の組織が親組織に提出する枚数を返す
// childrenは組織の関係を表す2次元配列(参照渡し)
int count_report_num(vector<vector<int>> &children, int x) {
// ベースケース
if (children.at(x).size() == 0) {
// 子組織から受け取ることは無いので1枚であることが確定している
return 1;
}
// 再帰ステップ
int sum = 0;
for (int c : children.at(x)) {
sum += count_report_num(children, c);
}
sum += 1; // x番の組織の報告書の枚数(1枚)を足す
return sum;
}
// これ以降の行は変更しなくてよい
int main() {
int N;
cin >> N;
vector<int> p(N); // 各組織の親組織を示す配列
p.at(0) = -1; // 0番組織の親組織は存在しないので-1を入れておく
for (int i = 1; i < N; i++) {
cin >> p.at(i);
}
// 組織の関係から2次元配列を作る
vector<vector<int>> children(N); // ある組織の子組織の番号一覧
for (int i = 1; i < N; i++) {
int parent = p.at(i); // i番の親組織の番号
children.at(parent).push_back(i); // parentの子組織一覧にi番を追加
}
// 各組織について、答えを出力
for (int i = 0; i < N; i++) {
cout << count_report_num(children, i) << endl;
}
}