Editorial: Deconstruction Tree

Read E0 first: statement, hints, and editorial.

E0 answers which vertices can appear in some achievable set, using only $\mathrm{sub}$ and a feasibility sweep on $\mathrm{pre}$. No distinct-set counting is required for E0.

E1 starts where E0 ends: keep the same preprocessing, but now $\mathrm{dp}$ and $\mathrm{pre}$ are used numerically to count distinct full sets.

Take sample 3 ($n = 7$):

        3
        |
        5 --- 7 --- 6 --- 1
              |
              4
              |
              2

The statement lists exactly three achievable sets:

• $\{3, 6, 7\}$
• $\{3, 4, 6, 7\}$
• $\{3, 4, 5, 6, 7\}$

Read off the pattern:

Sample 4 ($n = 10$) is richer: every achievable set contains $\{4, 9, 10\}$, while $5, 6, 7, 8$ appear in some but not all outcomes — $13$ total sets.

The counting problem is really: how many ways can we choose which optional branch leaders get stamped?

Run a DFS from root $n$. For each vertex $v \ne n$ define:

• $\mathrm{bel}[v]$ — the neighbor of $n$ on the unique path from $v$ to $n$. This is the branch id of $v$.
• $\mathrm{sub}[v]$ — the maximum label among all vertices in $v$’s subtree, where “subtree” means the side away from $n$ (standard rooted subtree).

Examples of meaning:

• If $\mathrm{sub}[v] \ge v$, some vertex below $v$ (farther from $n$) has label at least $v$. When that lower vertex is still a leaf, it beats $v$ as max leaf. Then $v$ never enters $S$.
• If $\mathrm{sub}[v] < v$, every vertex below $v$ on its branch is strictly smaller than $v$. Then $v$ is a branch champion: it can become max leaf once everything below it on that branch is cleared.

Only champions can contribute to distinct sets. Non-champions are invisible in the final sum.

Let $s$ be the maximum-index leaf. Round 1 always adds $s$ to $S$. No choice there.

After that, short branches often force the next stamp. In sample 4, after $4$ is added, the exposed leaves might be $\{1, 2, 3, 4\}$ with $4$ already used; you delete one of $1, 2, 3$, which advances those branches and round 2 always stamps one of $5, 6, 7$ depending on which leaf you removed.

So not all freedom is equal: side branches “commit” early. The long-run choices live on the branch that still has large champions ahead — the branch containing $n - 1$.

The key compression: after rooting at $n$, all remaining uncertainty can be swept in increasing order of vertex labels, starting from $s$.

Define arrays over labels $s, s + 1, \ldots, n - 1$:

• $\mathrm{dp}[i]$: number of new distinct set-patterns that first become available when champion $i$ is processed.
• $\mathrm{pre}[i] = \sum_{j=s}^{i}\mathrm{dp}[j]$: total number of distinct patterns formed up to label $i$.

So dp is an incremental contribution array, and pre is its prefix accumulator.

Base: $\mathrm{dp}[s] = 1$ (round 1 is fixed).

Transition: for $i > s$, if $i$ is not a champion ($\mathrm{sub}[i] \ge i$), set $\mathrm{dp}[i] = 0$. Otherwise:

Then $\mathrm{pre}[i] = \mathrm{pre}[i - 1] + \mathrm{dp}[i]$.

When champion $i$ is processed:

• $\mathrm{pre}[i - 1]$ counts all patterns built by earlier champions.
• Among them, patterns up to index $\mathrm{sub}[i]$ are already “spent” by the same-branch ancestor frontier.
• Only the difference creates genuinely new sets where $i$ changes the outcome.

Hence:

You do not need to trust the formula on first sight — verify it on samples (below). The recurrence is the whole combinatorics.

Let $B = \mathrm{bel}[n - 1]$ be the branch containing vertex $n - 1$ (the largest label besides $n$).

Other branches finish their race early. Let $\mathrm{other}$ be the largest vertex $i < n$ with $\mathrm{bel}[i] \ne B$. Intuitively, every branch $\ne B$ has “committed” by index $\mathrm{other}$.

The final answer is:

In words: sum $\mathrm{dp}[i]$ over champions on branch $B$ that lie after both $s$ and $\mathrm{other}$.

In both interesting samples this sum has a single term:

• Sample 3: $\mathrm{dp}[6] = 3$.
• Sample 4: $\mathrm{dp}[9] = 13$.

Branches from $7$: via $6$, via $4$, via $5$.

• $s = 3$ (max leaf). Round 1 stamps $3$.
• Champions include $4, 5, 6$ on their respective branches; $1, 2$ are not champions.
• $\mathrm{bel}[6] = 6$, $\mathrm{other} = 5$ (vertex $5$ is the largest-index vertex not on the same branch as $n - 1 = 6$).
• $\max(s, \mathrm{other}) = \max(3, 5) = 5$, so only champions with $i > 5$ on branch $B = 6$ count.
• Only $i = 6$ on branch $B = 6$ contributes: $\mathrm{dp}[6] = 3$.

The three sets match exactly the three ways the optional champions $4$ and $5$ on other branches interact with the forced core $\{3, 6, 7\}$.

Four branches from $10$, with leaves $1, 2, 3, 4$ and internal champions $5, 6, 7, 8, 9$ interleaved by label.

• $s = 4$. Round 1 stamps $4$.
• $\mathrm{dp}$ cascade on champions toward $9$:

• $\mathrm{bel}[9] = 9$, $\mathrm{other} = 8$, so sum starts at $i = 9$ only.
• Answer $= \mathrm{dp}[9] = 13$.

This matches the note: mandatory $\{4, 9, 10\}$, optional patterns among $\{5, 6, 7, 8\}$ with constraints, $13$ total.

For each test case:

1. Build the tree. Find $s$ = maximum-index leaf. If $s = n$, print $1$.
2. DFS from $n$ to fill $\mathrm{bel}[v]$ and $\mathrm{sub}[v]$.
3. For $i = s, s+1, \ldots, n-1$:
   • if $\mathrm{sub}[i] < i$, set $\mathrm{dp}[i] = \mathrm{pre}[i-1] - \mathrm{pre}[\mathrm{sub}[i]]$;
   • else $\mathrm{dp}[i] = 0$;
   • $\mathrm{pre}[i] = \mathrm{pre}[i-1] + \mathrm{dp}[i]$.
4. Find $\mathrm{other}$ = largest $i < n$ with $\mathrm{bel}[i] \ne \mathrm{bel}[n-1]$.
5. Sum $\mathrm{dp}[i]$ for $s < i < n$, $\mathrm{bel}[i] = \mathrm{bel}[n-1]$, $i > \max(s, \mathrm{other})$.

Output the sum modulo $998\,244\,353$.

Survival of $n$: argued in Step 2.

Characterization of $S$: a vertex is added exactly when it is max leaf at a round start; deleting a non-max leaf only shrinks other branches.

Champions only: if $\mathrm{sub}[v] \ge v$, a descendant leaf with label $\ge v$ can coexist while $v$ is a leaf, so $v$ can be deleted before winning.

DP recurrence: champions on a branch appear in increasing label order. When champion $i$ becomes the new frontier, configurations already counted at $\mathrm{sub}[i]$ do not produce new sets; subtracting $\mathrm{pre}[\mathrm{sub}[i]]$ leaves exactly the new extensions. Summing over the prefix gives $\mathrm{pre}[i-1] - \mathrm{pre}[\mathrm{sub}[i]]$.

Branch filter: branches $\ne B$ have finitely many leaves and no label $\ge n-1$. Their contribution is fixed once index passes $\mathrm{other}$. All remaining optional champions lie on $B$.

• DFS: $O(n)$.
• DP sweep: $O(n)$.
• Total per test: $O(n)$ time, $O(n)$ memory.
• Sum of $n$ over tests $\le 2 \cdot 10^5$.

E0 tells you who can ever win.
E1 uses the same sweep to count how many distinct winner-combinations survive after branch constraints.