아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

트리 위의 값

시간 제한1초메모리 제한512 MB

요약
트리의 공집합이 아닌 정점 부분집합 중 최대 정점 간 거리가 K인 것의 개수를 K=0부터 n-1까지 998244353으로 나눈 나머지로 구한다.
난이도

어려움10점 중 9점

유형
트리, 동적 계획법, 조합론, DFS
정답자
아직 제출이 없습니다

문제

정점이 nn개인 트리가 주어진다. 모든 간선의 길이는 정확히 1이다. 공집합이 아닌 정점 부분집합 SS에 대해 value(S)\mathit{value} (S)는 SS에 속하는 모든 쌍 (u,v)(u, v)에 대한 dis(u,v)\mathit{dis} (u, v)의 최댓값으로 정의한다. 여기서 dis(u,v)\mathit{dis} (u, v)는 트리에서 uu와 vv 사이의 거리이다.

value(S)\mathit{value} (S)는 0≤value(S)<n0 \le \mathit{value} (S) < n을 만족한다. 각 0≤K≤n−10 \le K \le n - 1에 대해 value(S)=K\mathit{value} (S) = K인 부분집합 SS의 개수를 출력하라.

입력

첫째 줄에는 정점의 개수 nn이 주어진다 (1≤n≤30001 \le n \le 3000). 이어서 n−1n - 1개의 줄이 주어지며, 각 줄에는 uu와 vv가 주어진다. 이는 uu와 vv 사이에 간선이 있음을 의미한다 (1≤u,v≤n1 \le u, v \le n). 주어진 그래프는 트리임이 보장된다.

출력

정확히 nn개의 정수를 한 줄에 출력한다. ii번째 정수는 value(S)=i−1\mathit{value} (S) = i - 1을 만족하는 공집합이 아닌 부분집합 SS의 개수여야 한다. 답이 매우 클 수 있으므로 각 답을 998 244 353998\,244\,353으로 나눈 나머지를 출력한다.

예제2

  1. 예제 1

    입력
    2
    1 2
    
    예상 출력
    2 1
    
  2. 예제 2

    입력
    4
    1 3
    2 4
    4 1
    
    예상 출력
    4 3 4 4