Computational Geometry - Hamiltonian Cycles on a Special Graph

Jiulian, an avid problem setter, has designed a problem mixing trees, depth-first search (DFS) order and computational geometry. You are given a rooted tree \(T\) with \(n\ (n\ge2)\) nodes (the root is node 1). A leaf is defined as any node (except the root) with degree exactly 1 in \(T\). First, a DFS traversal is performed on \(T\) starting at the root; when visiting a node, its children are explored in increasing order. Let \(A\) be the sequence of leaf nodes in the order of their first appearance in the DFS order.

For any two distinct leaves \(u\) and \(v\), if \(u\) is the \(i\)-th element in \(A\) and \(v\) is the \(j\)-th, define their cyclic distance as

[ d(u,v)=\min\Big(|i-j|,;|A|-|i-j|\Big). ]

Given an integer parameter \(K\), a new undirected simple graph \(G\) is constructed on the same \(n\) nodes. Two distinct nodes \(u\) and \(v\) are connected by an edge in \(G\) if at least one of the following conditions holds:

• \(u\) and \(v\) are connected by an edge in \(T\);
• Both \(u\) and \(v\) are leaves in \(T\) and \(d(u,v)\le K\).

Your task is to count the number of different Hamiltonian cycles in \(G\) modulo \(998244353\). A Hamiltonian cycle is defined as a subset of edges in \(G\) such that every vertex has exactly two incident edges and the graph is connected. Two Hamiltonian cycles are considered different if there is at least one edge that appears in one cycle and not in the other.

inputFormat

The first line contains two integers \(n\) and \(K\) separated by a space.

Each of the following \(n-1\) lines contains two integers \(u\) and \(v\) (\(1 \le u,v \le n\)) which denote an edge of the tree \(T\). It is guaranteed that \(T\) is a tree with node 1 as its root.

outputFormat

Output a single integer, the number of different Hamiltonian cycles in \(G\) modulo \(998244353\).

sample

2 1
1 2

0