Imitating the Key Tree
Contest: COMPFEST 14 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2800
Tags: combinatorics, dsu, trees

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 $$$[v_1, e_1, v_2, e_2, v_3, e_3, \ldots, 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 $$$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 $$$(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$$$ 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 $$$(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.

Print the answer modulo $$$998\,244\,353$$$.

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 format:
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 format:
An integer representing the number of distinct undirected weighted graphs that satisfy the conditions of the problem modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
The following is an example of a graph that satisfies.

The following is an assignment of edge weights in the key tree that corresponds to the graph above.

As an example, consider a pair of vertex indices $$$(1, 4)$$$.

- The circuit in the graph for this pair of vertices is $$$3 \xrightarrow{2} 2 \xrightarrow{4} 4 \xrightarrow{6} 2 \xrightarrow{1} 1 \xrightarrow{5} 3$$$ with a cost of $$$6$$$.
- The path in the key tree for this pair of vertices is $$$1 \xrightarrow{5} 3 \xrightarrow{6} 4$$$ with a cost of $$$6$$$.

Example input:
4
3 2
1 3
4 3

Example output:
540

Editorial:
Let's say we have two graphs, each having $$$N$$$ vertices. Initially, there are no edges. We want to make the first graph into a graph that satisfies the condition of the problem and make the second graph into the key tree with a weight assignment that corresponds to the first graph.
Sequentially for each $$$k$$$ from $$$1$$$ to $$$2N-2$$$, do all of the following:
• Add an edge with weight $$$k$$$ to the first graph.
• Choose one of the following:   Add an edge with weight $$$k$$$ to the second graph.  Do nothing.
• Add an edge with weight $$$k$$$ to the second graph.
• Do nothing.
In order to make the second graph into the key tree, we must add exactly $$$N-1$$$ edges to it throughout the process and the $$$i$$$-th edge added is edge $$$i$$$ of the key tree.
In an iteration, if we choose to not add an edge to the second graph, it can be obtained that the edge added to the first graph must not merge any biconnected components. Let's call this type of edge in the first graph an idle edge.
Otherwise, if we choose to add an edge to the second graph, it can be obtained that the following must be satisfied:
• Let $$$c_1$$$ and $$$c_2$$$ be the connected components of the second graph that are merged by adding the new edge.
• The edge added to the first graph must merge exactly two biconnected components, each of them containing vertices with the same indices as the ones in each of $$$c_1$$$ and $$$c_2$$$.
• Let's call this type of edge in the first graph a connector edge. We can see that there must be exactly $$$N-1$$$ connector edges in the first graph.
The only way to make it such that adding an edge connects exactly two biconnected components is to already have exactly one existing edge connecting the two biconnected components. Let's call this type of existing edge a helper edge.
It can be obtained that an edge cannot be a helper edge of more than one connector edge. Because we only have $$$2N-2$$$ edges for the first graph, those edges must only consist of $$$N-1$$$ connector edges and $$$N-1$$$ helper edges. This means all helper edges must be idle edges. But it can be obtained that each helper edge in our construction is always an idle edge.
The $$$i$$$-th connector edge and its corresponding helper edge must connect the two biconnected components that correspond to the two connected components merged using edge $$$i$$$ of the key tree. If the sizes of the connected components are $$$s_1$$$ and $$$s_2$$$, then there are $$$(s_1 \times s_2)^2$$$ possible pairs of connector and helper edges.
The number of ways to choose which edge to add in each iteration is the same as the number of ways to colour a sequence of $$$2N-2$$$ elements with $$$N-1$$$ colours (numbered from $$$1$$$ to $$$N-1$$$) such that:
• Each colour occurs in exactly $$$2$$$ elements.
• For each pair of colours $$$(i, j)$$$, if $$$i<j$$$, then the latest element with colour $$$i$$$ must occur earlier than the latest element with colour $$$j$$$.
We can see that the number of ways is $$$\frac{(2N-2)!}{(2!)^{N-1}\times (N-1)!}$$$. To get the answer to the problem, we just multiply this value by each of the $$$(s_1 \times s_2)^2$$$ for each merged pair of connected components in the key tree.
Time complexity: $$$O(N)$$$