Universal Cup Judging System

Universal Cup

時間限制: 8.0 s 記憶體限制: 256 MB 總分: 100 可 Hack ✓
统计

Aleksei는 생일 선물로 크기가 $n$인 사과나무를 받았습니다. 경쟁적 프로그래머인 그는 나무에서 만들 수 있는 $k$-사과파이의 개수를 계산해 보기로 했습니다.

크기가 $n$인 사과나무는 정점 $1$을 루트로 하고 $n$개의 정점을 가지는 루트 있는 트리로 정의되며, 여기서 (부모가 없는 루트를 제외한) 각 정점은 자신의 부모보다 직접적인 자식 정점의 수가 엄격히 적습니다.

$k$-사과파이는 다음 조건을 만족하는 쌍 $(v, S)$입니다:

  • $v \in V$는 트리의 한 정점(중심)입니다.
  • $S \subset V \setminus \{v\}$는 크기가 $k - 1$인 정점들의 집합입니다.
  • 모든 $u \in S$에 대해 $\text{dist}(v, u) = d$를 만족하는 정수 $d$가 존재합니다.

거리 $\text{dist}(u, v)$는 정점 $u$와 $v$ 사이의 단순 경로에 있는 간선의 개수로 정의됩니다.

즉, $k$-사과파이는 하나의 정점 $v$(중심)와 $v$로부터의 거리가 모두 같은 다른 $k - 1$개의 정점으로 이루어집니다.

당신의 과제는 주어진 트리에서 $k$-사과파이의 개수를 구하는 것입니다.

답이 매우 클 수 있으므로, $998\,244\,353$으로 나눈 나머지를 출력하십시오.

입력

각 테스트는 여러 개의 테스트 케이스를 포함합니다. 첫 번째 줄에는 테스트 케이스의 개수 $t$ ($1 \le t \le 10^4$)가 주어집니다. 이어서 테스트 케이스의 설명이 주어집니다.

각 테스트 케이스는 사과나무의 정점 개수와 사과파이의 크기를 나타내는 두 정수 $n$과 $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$)가 포함된 줄로 시작합니다.

다음 줄에는 $n - 1$개의 정수 $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$)이 주어지며, 여기서 $p_i$는 사과나무에서 정점 $i$의 부모를 나타냅니다.

모든 테스트 케이스에 걸친 $n$의 합은 $5 \cdot 10^5$을 초과하지 않습니다.

출력

각 테스트 케이스마다 $k$-사과파이의 개수를 $998\,244\,353$으로 나눈 나머지를 나타내는 정수 하나를 출력합니다.

예제

입력 1

3
3 3
1 1
5 2
1 1 2 3
6 3
1 1 1 2 2

출력 1

1
20
16

참고

첫 번째 테스트 케이스에서 유일하게 존재하는 파이는 정점 $1$을 중심으로 하며, 이에 대응하는 집합은 $S = \{2, 3\}$입니다.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#2360EditorialOpenNew Editorial for Problem #14130cqbzzlrView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.