[Solution] Imitating the Key Tree Codeforces Solution

I. Imitating the Key Tree

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Pak Chanek has a tree called the key tree. This tree consists of 𝑁$N$ vertices and 𝑁−1$N-1$ edges. The edges of the tree are numbered from 1$1$ to 𝑁−1$N-1$ with edge 𝑖$i$ connecting vertices 𝑈𝑖$U_i$ and 𝑉𝑖$V_i$. Initially, each edge of the key tree does not have a weight.

Formally, a path with length 𝑘$k$ in a graph is a sequence [𝑣1,𝑒1,𝑣2,𝑒2,𝑣3,𝑒3,…,𝑣𝑘,𝑒𝑘,𝑣𝑘+1]$[v_1,e_1,v_2,e_2,v_3,e_3,\dots ,v_k,e_k,v_{k+1}]$ such that:

• For each 𝑖$i$, 𝑣𝑖$v_i$ is a vertex and 𝑒𝑖$e_i$ is an edge.
• For each 𝑖$i$, 𝑒𝑖$e_i$ connects vertices 𝑣𝑖$v_i$ and 𝑣𝑖+1$v_{i+1}$.

A circuit is a path that starts and ends on the same vertex.

A path in a graph is said to be simple if and only if the path does not use the same edge more than once. Note that a simple path can use the same vertex more than once.

The cost of a simple path in a weighted graph is defined as the maximum weight of all edges it traverses.

Count the number of distinct undirected weighted graphs that satisfy the following conditions:

• The graph has 𝑁$N$ vertices and 2𝑁−2$2N-2$ edges.
• For each pair of different vertices (𝑥,𝑦)$(x,y)$, there exists a simple circuit that goes through vertices 𝑥$x$ and 𝑦$y$ in the graph.
• The weight of each edge in the graph is an integer between 1$1$ and 2𝑁−2$2N-2$ inclusive. Each edge has distinct weights.
• The graph is formed in a way such that there is a way to assign a weight 𝑊𝑖$W_i$ to each edge 𝑖$i$ in the key tree that satisfies the following conditions:
  • For each pair of edges (𝑖,𝑗)$(i,j)$, if 𝑖<𝑗$i<j$, then 𝑊𝑖<𝑊𝑗$W_i<W_j$.
  • For each pair of different vertex indices (𝑥,𝑦)$(x,y)$, the cost of the only simple path from vertex 𝑥$x$ to 𝑦$y$ in the key tree is equal to the minimum cost of a simple circuit that goes through vertices 𝑥$x$ and 𝑦$y$ in the graph.
• Note that the graph is allowed to have multi-edges, but is not allowed to have self-loops.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

Print the answer modulo 998244353$998244353$.

Two graphs are considered distinct if and only if there exists a triple (𝑎,𝑏,𝑐)$(a,b,c)$ such that there exists an edge that connects vertices 𝑎$a$ and 𝑏$b$ with weight 𝑐$c$ in one graph, but not in the other.

Input

The first line contains a single integer 𝑁$N$ (2≤𝑁≤105$2\le N\le {10}^5$) — the number of vertices in the key tree.

The 𝑖$i$-th of the next 𝑁−1$N-1$ lines contains two integers 𝑈𝑖$U_i$ and 𝑉𝑖$V_i$ (1≤𝑈𝑖,𝑉𝑖≤𝑁$1\le U_i,V_i\le N$) — an edge connecting vertices 𝑈𝑖$U_i$ and 𝑉𝑖$V_i$. The graph in the input is a tree.

Output

An integer representing the number of distinct undirected weighted graphs that satisfy the conditions of the problem modulo 998244353$998244353$.