Editorial (easy): E0. Who can win the max leaf?

For each vertex $v$, output Y if $v$ can appear in at least one achievable final set $S$, else N.

You are not counting how many distinct sets exist. That is E1.

Each round:

1. Add the current maximum-index leaf to $S$.
2. Delete a different leaf.

So:

Vertex $v$ is Y iff you can schedule deletions so that, in some round, $v$ is that max leaf.

Always Y

• $n$ (largest label, never deleted).
• $s$ = maximum-index leaf in the initial tree (round 1 is forced).

Trivial whole test

• If $s = n$, every round is forced. Only $n$ is ever stamped: output N...NY.

Usually N

Root the tree at $n$. For $v \ne n$, let $\mathrm{sub}[v]$ be the maximum label in $v$’s subtree away from $n$.

If $\mathrm{sub}[v] \ge v$, some descendant on the same branch has label at least $v$. While that descendant can still appear as a leaf, it beats $v$ as max leaf, so you can always delete $v$ before it wins. Then $v$ is N.

If $\mathrm{sub}[v] < v$, call $v$ a branch champion: every vertex farther out on that branch is smaller.

Vertex $n - 1$ can be Y even when $\mathrm{sub}[n - 1] > n - 1$ (so it is not a champion): a larger label sits below it on its branch, but once that child is cleared, $n - 1$ can still become max leaf. This happens on path-like trees.

Rule: mark $n - 1$ as Y when $\mathrm{sub}[n - 1] > n - 1$ and $s \ne n$.

Being a champion is necessary but not sufficient.

Example ($n = 7$, sample 3): vertices $4$ and $5$ are champions and both are Y, but vertex $1$ is a champion on a dead side branch and is N.

Champions are processed in increasing label order starting from $s$. When champion $v$ becomes relevant:

• all smaller-label champions have already shaped which leaves the other branches expose;
• on $v$’s own branch, the last active frontier below $v$ is $\mathrm{sub}[v]$.

Vertex $v$ can win in some play iff there is still at least one partial schedule among earlier champions that is not already frozen by the time the frontier was at $\mathrm{sub}[v]$.

You do not need to list those schedules. You only need a yes/no test.

Run the same DFS from $n$ as in E1 to fill $\mathrm{sub}[\cdot]$.

Then sweep labels $i = s, s + 1, \ldots, n - 1$ and maintain one integer array $\mathrm{pre}[i]$:

• meaning: how many partial play outcomes are possible after processing all champions with label at most $i$;
• in E0 you never use the actual number for the final answer — only comparisons.

Build $\mathrm{pre}$ for labels $1, 2, \ldots, s - 1$ with the same update (start from $\mathrm{pre}[0] = 0$).

Set $\mathrm{pre}[s] = 1$ (round 1 fixes $s$).

For $i > s$:

• if $\mathrm{sub}[i] \ge i$ (not a champion): $\mathrm{pre}[i] = \mathrm{pre}[i - 1]$;
• else let $\mathrm{add} = \mathrm{pre}[i - 1] - \mathrm{pre}[\mathrm{sub}[i]]$ and set $\mathrm{pre}[i] = \mathrm{pre}[i - 1] + \mathrm{add}$.

Membership for champion $v$:

Equivalently, the increment $\mathrm{add}$ at $i = v$ would be positive. That is the entire feasibility test.

E1’s answer is built from the numeric values of the same sweep (how many distinct full sets remain at the end).

E0 only asks: “is the increment at $v$ positive?” — i.e. can $v$ still matter in at least one partial outcome?

No prefix sum of distinct sets is required for the problem statement; one array $\mathrm{pre}$ is enough.

1. Find $s$ = max-index leaf. Mark $n$ and $s$ as Y. If $s = n$, print and stop.
2. DFS from $n$ for $\mathrm{sub}[v]$.
3. Build $\mathrm{pre}$ with the sweep above.
4. For each $v < n$:
   • if $\mathrm{sub}[v] < v$ and $\mathrm{pre}[v - 1] > \mathrm{pre}[\mathrm{sub}[v]]$: Y;
   • else if $v = n - 1$ and $\mathrm{sub}[v] > v$ and $s \ne n$: Y;
   • else if $v \notin \{n, s\}$: N.

Achievable sets: $\{3,6,7\}$, $\{3,4,6,7\}$, $\{3,4,5,6,7\}$.

Output: NNYYYYY.

E0 classifies vertices with one comparison per champion.

E1 reuses the same $\mathrm{pre}$ sweep but keeps the numeric increments and sums them on the branch of $n - 1$ after index $\mathrm{other}$. See editorial.md.

$O(n)$ time and $O(n)$ memory per test case.