시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
서브태스크 참고 (추가 시간 없음) | 1024 MB | 35 | 18 | 14 | 51.852% |
Amadea and Bilva are decorating a rooted tree containing N nodes, labelled from 1 to N. Node 1 is the root of the tree, and all other nodes have a node with a numerically smaller label as their parent.
Amadea and Bilva's decorate the tree as follows:
The beauty of the tree is equal to the number of nodes painted at least once by either Amadea or Bilva. Note that even if they both paint a node, it only counts once.
What is the expected beauty of the tree?
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the three integers N, A and B. The second line contains N-1 integers. The i-th integer is the parent of node i+1.
For each test case, output one line containing Case #x: y
, where x
is the test case number (starting from 1) and y
is the expected beauty of the tree.
y
will be considered correct if it is within an absolute or relative error of 10-6 of the correct answer.
시간 제한: 20 초
시간 제한: 40 초
3 8 2 3 1 1 3 4 4 3 4 10 3 4 1 1 1 1 1 1 1 1 1 4 3 1 1 2 3
Case #1: 2.65625 Case #2: 1.9 Case #3: 2.875
The trees for each sample case are shown in the diagram below.
A few example colourings for sample case #1 are shown below.
Contest > Google > Kick Start > Google Kick Start 2020 > Round D C번