No.2471 Gemini Tree(Ver.Lapislazuli)
Problem Statement
Consider a tree in which either a green stone or a blue stone is placed on each vertex. Among such trees, a tree is called a "Gemini Tree" if it is possible for condition 3. to be satisfied when operations 1 and 2 below are performed.
- First, perform the operation "choose a pair of vertices directly connected by an edge and swap the stones placed on them" any number of times, possibly zero.
- Next, choose at most one edge and delete it.
- At this point, the tree has been split into at most 2 connected components, and in each connected component, the stones placed are all of one kind.
You are given a tree with $N$ vertices with no stones placed on it. There are $2^N$ ways to place one stone on each vertex. How many of these placements satisfy the following condition?
- It is possible to perform $1$ time the operation of choosing one leaf of the tree and removing it (together with the stone placed on it). However, the tree must be a "Gemini Tree" both before and after the operation.
Input
$N$
$u_1\ v_1$
$\vdots$
$u_{N-1}\ v_{N-1}$
- All inputs are integers
- $2 \le N \le 10^5$
- $1 \le u_i,v_i \le N$
- The given graph is a tree
Output
Output the remainder of the answer divided by $998244353$ on one line.
Print a newline at the end.
Sample
Sample 1
Input
3 1 2 2 3
Output
8
All placements satisfy the condition.
Sample 2
Input
4 1 2 1 3 1 4
Output
10
There are 10 initial placements that are a "Gemini Tree". For all of them, the tree can still be a "Gemini Tree" after removing one leaf.
Sample 3
Input
7 1 2 1 3 1 4 2 5 2 6 2 7
Output
84
There are 86 initial placements that are a "Gemini Tree". Of these, 2 will not be a "Gemini Tree" no matter which leaf is removed.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
SPD_9X2
akakimidori
りあん
tsutaj
beet
tute7627
nok0
だれ
momoyuu