트리 위의 값
시간 제한1초메모리 제한512 MB
트리의 공집합이 아닌 정점 부분집합 중 최대 정점 간 거리가 K인 것의 개수를 K=0부터 n-1까지 998244353으로 나눈 나머지로 구한다.
문제
정점이 개인 트리가 주어진다. 모든 간선의 길이는 정확히 1이다. 공집합이 아닌 정점 부분집합 에 대해 는 에 속하는 모든 쌍 에 대한 의 최댓값으로 정의한다. 여기서 는 트리에서 와 사이의 거리이다.
는 을 만족한다. 각 에 대해 인 부분집합 의 개수를 출력하라.
입력
첫째 줄에는 정점의 개수 이 주어진다 (). 이어서 개의 줄이 주어지며, 각 줄에는 와 가 주어진다. 이는 와 사이에 간선이 있음을 의미한다 (). 주어진 그래프는 트리임이 보장된다.
출력
정확히 개의 정수를 한 줄에 출력한다. 번째 정수는 을 만족하는 공집합이 아닌 부분집합 의 개수여야 한다. 답이 매우 클 수 있으므로 각 답을 으로 나눈 나머지를 출력한다.