## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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 $N-1$ edges. The edges of the tree are numbered from $1$ to $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 $\left[{v}_{1},{e}_{1},{v}_{2},{e}_{2},{v}_{3},{e}_{3},\dots ,{v}_{k},{e}_{k},{v}_{k+1}\right]$ 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 ${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 $2N-2$ edges.
• For each pair of different vertices $\left(x,y\right)$, 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$ and $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 $\left(i,j\right)$, if $i, then ${W}_{i}<{W}_{j}$.
• For each pair of different vertex indices $\left(x,y\right)$, 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:-  👉
👇👇👇👇👇

Print the answer modulo $998\phantom{\rule{thinmathspace}{0ex}}244\phantom{\rule{thinmathspace}{0ex}}353$.

Two graphs are considered distinct if and only if there exists a triple $\left(a,b,c\right)$ 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\le N\le {10}^{5}$) — the number of vertices in the key tree.

The $i$-th of the next $N-1$ lines contains two integers ${U}_{i}$ and ${V}_{i}$ ($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 $998\phantom{\rule{thinmathspace}{0ex}}244\phantom{\rule{thinmathspace}{0ex}}353$.