問題一覧 > 通常問題

No.2471 Gemini Tree(Ver.Lapislazuli)

レベル : / AI推定難易度 : 2500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 5
作問者 : SPD_9X2 / テスター : akakimidori りあん tsutaj beet 👑 tute7627 nok0 👑 rin204 だれ momoyuu KKT89
お気に入りにしたユーザー ProblemId : 9825 / 自分の提出
問題文最終更新日: 2023-11-28 23:06:17
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Japan Alumni Group Summer Camp 2023 Day 2 (順位表) の他の問題:

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.

  1. 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.
  2. Next, choose at most one edge and delete it.
  3. 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.
The answer can be very large, so output the remainder when it is divided by $998244353$.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。