問題一覧 > 通常問題

No.3346 Tree to DAG

レベル : / AI推定難易度 : 2500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 15
作問者 : n_bitand_n_per_3 / テスター : Nzt3 jupiter_68 noya2
お気に入りにしたユーザー ProblemId : 12801 / 自分の提出
問題文最終更新日: 2025-11-13 19:33:06
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
yukicoder contest 作問ハッカソンコンテスト 003 Day1 (順位表) の他の問題:

Problem Statement

You are given an undirected tree with $N$ vertices numbered from $1$ to $N$. The $i$-th edge connects vertex $u _i$ and vertex $v_i$.

First, you choose $3$ distinct vertices $a,b,c$. Then, you add vertex $0$ to the graph and connect vertex $0$ and vertex $a$, vertex $0$ and vertex $b$, and vertex $0$ and vertex $c$ with edges. Call the graph obtained in this way $G_{a,b,c}$. The graph $G_{a,b,c}$ contains $N+2$ edges, and we now assign a direction to each of them. Formally, for every edge, an edge connecting vertices $u,v$ is replaced with exactly one of the directed edge $u \rightarrow v$ or the directed edge $v \rightarrow u$. Depending on the assignment, $2^{N+2}$ directed graphs are obtained; let $f(G_{a,b,c})$ be the number of those that are DAGs (directed acyclic graphs).

Output the maximum value of $f(G_{a,b,c})$ over appropriate choices of $a,b,c$, modulo $998244353$.

Constraints

  • $3 \le N \le 10^5$
  • $1 \le u_i,v_i \le N \ (1 \le i \le N-1)$
  • The given graph is a tree.
  • All input values are integers.

Input

The input is given from standard input in the following format.
$N$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_{N-1}\ v_{N-1}$
  • Line $1$ contains an integer $N$, the number of vertices of the tree.
  • Lines $2$ through $N$ contain the information on the edges of the tree. Among them, line $i+1 (1≦i≦N-1)$ contains a pair of integers $u_i, v_i$, indicating that vertices $u_i$ and $v_i$ are connected by an edge.
  • It is guaranteed that the $N$ vertices form a tree.

Output

Output the answer in $1$ line.

Sample

Sample 1
Input
3
1 2
2 3
Output
18

If vertices $1,2,3$ are taken as $a,b,c$ in this order, the graph $G_{a,b,c}$ looks like the figure below.

When assigning directions to the 5 edges, the result is a DAG in cases such as the following.

The result is not a DAG in cases such as the following.

For this sample, there are $18$ assignments in total that result in a DAG.
Sample 2
Input
11
1 2
2 4
4 6
4 7
1 3
3 5
3 9
9 8
9 10
9 11
Output
7536

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。