Gemini Tree (Ver.Lapislazuli)

시간 제한2초메모리 제한1024 MB

요약

트리의 정점을 두 색으로 칠하는 2^N가지 경우 중, 원래 트리와 리프 하나를 제거한 트리가 모두 주어진 교환 및 절단 조건에서 Gemini 트리가 되는 경우의 수를 센다.

난이도: 어려움10점 중 8점
유형: 트리, DFS, 조합론, 동적 계획법
정답자: 아직 제출이 없습니다

문제

Consider a tree with a green or blue stone placed at each vertex. Such a tree is called a "Gemini Tree" if condition 3 can be satisfied after performing the following operations 1 and 2.

First, operate "selecting pairs of vertices that are directly connected by edges and exchanging the stones placed on each endpoint," any number of times from zero to more.
Second, select one or fewer edges and delete them.
At this time, the tree is divided into at most two connected components, and only one type of stone is placed in either.

You are given an $N$ -vertex tree with no stones. There are $2^N$ ways to place one stone at each vertex. How many of them satisfy the following condition?

Select one leaf and remove it with the stone placed. The tree must be a "Gemini tree" before and after the operation.

Output the remainder of the answer after dividing by $998244353$ because it can be large.

입력

$N$

$u\_1$ $v\_1$

$\vdots$

$u\_{N-1}$ $v\_{N-1}$

출력

Output the remainder of the answer after dividing by $998244353$ in one line. Add a new line at the end of the output.

제한

All inputs consist of integers.
$2 \le N \le 10^5$
$1 \le u\_i, v\_i \le N$
The given graph is a tree.

힌트

In Sample Input 1, All of the stone placements satisfy the condition.

In Sample Input 2, there are 10 different ways that the first placement is "Gemini Tree." They could also be "Gemini Tree" after one leaf is removed.

In Sample Input 3, there are 86 ways that the first placement is a "Gemini Tree." Two of these are not "Gemini Tree," if any one leaf is removed.

예제3

예제 1
입력
```
3
1 2
2 3
```
예상 출력
```
8
```
예제 2
입력
```
4
1 2
1 3
1 4
```
예상 출력
```
10
```
예제 3
입력
```
7
1 2
1 3
1 4
2 5
2 6
2 7
```
예상 출력
```
84
```