독립 집합 (합)

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

요약

트리에서 서로 인접하지 않은 노드 집합 중 공집합이 아닌 모든 집합의 점수, 즉 노드 개수와 연결에 필요한 최소 간선 수의 곱을 모두 더한 값을 998244353으로 나눈 나머지를 구합니다.

난이도: 보통10점 중 7점
유형: 트리, 동적 계획법, 조합론
정답자: 아직 제출이 없습니다

문제

노드가 $N$ 개인 트리가 주어진다. 노드 번호는 $1$ 부터 $N$ 까지이다. 간선은 $1$ 번부터 $N-1$ 번까지 번호가 붙어 있으며, $i$ 번 간선은 노드 $U_i$ 와 $V_i$ 를 잇는다.

공집합이 아닌 노드 집합이 독립 집합이라는 것은 집합에 속한 노드 중 서로 인접한 노드가 없다는 뜻이다. 첫 번째 그림에서 빨간색 노드가 집합의 원소이다.

독립 집합의 점수는 집합의 노드 수와, 집합의 모든 노드를 연결하는 최소 간선 수의 곱이다. 두 번째 그림은 노드가 2개이고 연결에 필요한 최소 간선 수가 3인 경우를 보여 준다. 이때 점수는 $2 \cdot 3 = 6$ 이다. 노드가 하나뿐인 집합의 점수는 $0$ 이다.

트리에 있는 공집합이 아닌 모든 독립 집합의 점수 합을 구하라. 결과가 매우 클 수 있으므로 $998244353$ 으로 나눈 나머지를 출력한다.

입력

첫째 줄에 정수 $N$ ( $2 \le N \le 100000$ )이 주어진다.

다음 $N-1$ 개의 줄에는 두 정수 $U_i$ 와 $V_i$ ( $1 \le U_i, V_i \le N$ )가 주어진다. 주어지는 간선들은 트리를 이룬다.

출력

공집합이 아닌 독립 집합들의 점수 합을 $998244353$ 으로 나눈 나머지를 한 줄에 출력한다.

예제2

예제 1
입력
```
5
1 2
1 3
3 4
3 5
```
예상 출력
```
49
```
예제 2
입력
```
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
```
예상 출력
```
616
```