Editorial: Deconstruction Tree

This problem looks like “do something $n - 1$ times, make choices, count outcomes.” That is intentionally under-specified. A useful meta-strategy:

1. Simulate tiny cases until you see a pattern in what ends up in $S$.
2. Rephrase the process in one sentence you can reuse (here: vertices that ever win “max leaf”).
3. Find an anchor — a vertex or structure that never changes (here: $n$ always survives).
4. Root the tree and describe the process locally on branches.
5. Classify vertices into always / sometimes / never before writing any DP.
6. Compress the remaining freedom to the smallest parameter (here: a 1D sweep over labels on one branch).

The rest of this editorial is that discovery path, written in the order you might explain it in a video.

Each round:

1. Let $x$ be the leaf with maximum index.
2. Insert $x$ into $S$ (duplicates do nothing).
3. Delete some other leaf.

So $S$ is not “vertices we deleted” or “vertices that stayed.” It is:

$S$ = set of vertices that were the maximum-index leaf at the start of some round.

Once you say that out loud, the problem becomes combinatorial: which subsets of $\{1, \ldots, n\}$ can occur as “winners of the max-leaf race” under some valid sequence of deletions?

Vertex $n$ has the largest label in the whole tree.

• If $n$ is a leaf, it is the max leaf that round and cannot be chosen for deletion.
• If $n$ is not a leaf, only leaves are deleted anyway.

Therefore $n$ is never removed and $n \in S$ always.

When is everything forced? If $n$ itself is a leaf initially, the tree is just an edge hanging off $n$ (or a path ending at $n$). Then every round picks max leaf $n$ first among the remaining leaves, and the other endpoint is deleted — no choices. The answer is $1$.

We will use:

• $s$ = the maximum-index leaf in the initial tree.
• Early exit: if $s = n$, answer $= 1$.

Root the tree at $n$. Each neighbor of $n$ starts a branch.

At any moment in the process:

• Each branch exposes one current leaf (the unique leaf of that branch in the remaining forest).
• The global max leaf is the maximum label among those exposed leaves.
• That max leaf is added to $S$, then you delete a different leaf.

Picture several “runners” (branches), each showing one label. The largest label wins and gets stamped into $S$. You choose which non-winning runner to eliminate, which advances that branch inward.

This mental model is the whole geometry of the problem.

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 answer.

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 $\mathrm{dp}[ \cdot ]$ and prefix sums $\mathrm{pre}[ \cdot ]$ over vertex labels (we only need indices $s, s+1, \ldots, n-1$).

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$ becomes relevant, every distinct set counted in $\mathrm{pre}[i - 1]$ already includes all decisions among earlier champions. But some of those were already determined back when the previous leader $\mathrm{sub}[i]$ on the same branch was the active frontier. Subtracting $\mathrm{pre}[\mathrm{sub}[i]]$ is inclusion–exclusion: keep only configurations that make a fresh choice at $i$.

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$.

Problems that say “repeat this local rule” often become easy once you:

1. Name the invariant ($S$ = max-leaf winners).
2. Find the immovable object ($n$).
3. Draw the picture (branches racing by label).
4. Classify participants (always / sometimes / never).
5. Compress to one dimension (label sweep on the main branch).

The DP formula looks mysterious in isolation. In a video, derive it last — after the audience already believes only champions on branch $B$ matter and that earlier champions “use up” configurations counted at $\mathrm{sub}[i]$.

That order — simulate, rephrase, anchor, picture, classify, compress — is reusable far beyond this one task.