dlaud5379   7달 전

(Kagi Translate로 번역한 텍스트를 다듬었습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)

문제

BOJ에 있는 문제를 본 블롭은 쉬는 시간에 이런 인터랙티브 문제를 생각해 냈다.

한별이는 무향 비순환 연결 그래프, 즉 트리 하나를 선물받았다. 트리의 노드에는 1번부터 N번까지 번호가 붙어 있으며, 1번 노드는 루트이다. 트리의 각 노드는 정확히 하나의 부모를 가지지만, 예외적으로 루트 노드는 부모를 가지지 않는다. 자식이 하나도 없는 노드를 리프 노드라고 한다. 한별이는 루트 노드를 제외한 모든 노드의 부모를 알고 있다. 즉, 트리 전체의 구조를 알고 있다.

각 노드는 정수 값을 가진다. 리프 노드를 제외한 각 노드의 값은 자신과 직접 연결된 자식 노드의 값의 합이다. 즉, 트리의 모든 노드의 값은 리프 노드의 값에 의해 결정된다.

preview

한별이는 아직 어떤 노드의 값도 알지 못하기 때문에, 최소 개수의 노드를 열어서 값을 확인해 보려고 한다. 한별이를 도와서 최소한의 노드만 열어서 모든 노드의 값을 구하는 프로그램을 작성해 보자!

이 문제는 블롭에게 너무 쉬웠고, 블롭은 문제의 마지막 문장을 다음과 같이 바꿨다.

한별이가 모든 노드의 값을 구하기 위해 열어야 하는 노드의 집합 중 크기가 가장 작은 것을 '최소 조회 집합'이라 할 때, 주어진 트리에 대해 서로 다른 최소 조회 집합의 개수를 구하는 프로그램을 작성해 보자!

이제 이 문제는 블롭에게 너무 어려워서 풀 수 없었다!

블롭을 위해 최소 조회 집합의 개수를 구하자.

입력

첫 번째 줄에 N이 주어진다. (2 ≤ N ≤ 105)

두 번째 줄에 N-1개의 정수가 공백으로 구분되어 주어진다. 이 중 i번째 정수는 i+1번 노드의 부모이다. (1 ≤ Pi ≤ N)

출력

주어진 트리의 최소 조회 집합의 개수를 109 + 7로 나눈 나머지를 출력한다.

댓글을 작성하려면 로그인해야 합니다.