← 返回题目列表

AtCoder · APG4b_cc

EX20. 第2.05节

中文机器翻译题面 查看原题
page_url:https://atcoder.jp/contests/apg4b/tasks/APG4b_cc

返回说明页面

报告数量

問題文

您是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;
  }
}