Walk Alone has a binary tree
T with
n nodes labelled from
1 to
n rooted at node
1. Each node
u in the tree has at most two children, the left child
ℓT,u and the right child
rT,u where
ℓT,u denotes the label of the left child and
ℓT,u=0 if
u does not have a left child, and
rT,u similarly. We omit the subsc
ript T if T is clear from the context. The right child of u exists only if u has a left child.
He once performed an operation named left-child right-sibling (LCRS) transform on the tree for exactly k times. In each operation, he would
-
Visit all vertices in descending order of depth. For each vertex u with two children ℓu and ru, remove edge (u,ru) and let the right child of ℓu be ru. It can be shown that ℓu does not have a right child at this time.
-
For each vertex u with a right child and no left child, i.e., ru≠0 and ℓu=0, swap ℓu and ru.
You can refer to the following code for better understanding.
void dfs(int u) {
// l[u]/r[u]: The left/right child of node u
// Recursively visit all children of node u
if (l[u] != 0) dfs(l[u]);
if (r[u] != 0) dfs(r[u]);
if (r[u] != 0) {
// Here l[u] != 0 because r[u] != 0
if (l[l[u]] == 0) l[l[u]] = r[u];
else r[l[u]] = r[u];
r[u] = 0;
}
}
void LCRS() {
dfs(1);
}
However, he forgot what the original tree is like. Now he wants you to tell him the number of different possible initial trees modulo 998244353998. Two trees T1 and T2 are considered different if and only if there exists a node u such that (ℓT1,u,rT1,u)≠(ℓT2,u,rT2,u).