No.3346 Tree to DAG
タグ : / 解いたユーザー数 15
作問者 :
noya2
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.

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