Hints (easy): E0. Who can win the max leaf?
Y/N per vertex. You do not count how many distinct sets exist.
Answer to Hint 1: Each round adds the current maximum-index leaf to $S$, then deletes another leaf.
So $v$ is Y iff you can make $v$ the maximum-index leaf at the start of some round.
Answer to Hint 2: Two vertices are always Y:
- $n$ (never deleted),
- $s$ = maximum-index leaf in the initial tree (round 1 is forced).
If $s = n$, only $n$ ever gets stamped.
Answer to Hint 3: Root at $n$. Let $\mathrm{sub}[v]$ be the maximum label in $v$’s subtree away from $n$.
If $\mathrm{sub}[v] \ge v$, a descendant can beat $v$ as max leaf forever, so $v$ is N.
If $\mathrm{sub}[v] < v$, call $v$ a branch champion (still not automatically Y).
Y even when $\mathrm{sub}[n - 1] > n - 1$ (not a champion), as long as $s \ne n$. After its heavy child is removed, $n - 1$ can still win once.
Answer to Hint 5: For a champion $v$, ask: is there any valid timing of earlier deletions so $v$ can become global max leaf?
Process champions in increasing label order from $s$. Maintain $\mathrm{pre}[i]$ = how many partial outcomes are still possible after champions up to label $i$.
Answer to Hint 6: Build $\mathrm{pre}$ from label $1$ up to $s - 1$, then set $\mathrm{pre}[s] = 1$, then continue to $n - 1$. At each champion label $i$, use the same update
$$ \mathrm{pre}[i] = \mathrm{pre}[i - 1] + (\mathrm{pre}[i - 1] - \mathrm{pre}[\mathrm{sub}[i]]). $$For E0 you only need the comparison: champion $v$ is Y iff $\mathrm{pre}[v - 1] > \mathrm{pre}[\mathrm{sub}[v]]$ (for $v \ge 2$).
Answer to Hint 7: Full E0 checklist per vertex:
- $v = n$ or $v = s$ →
Y. - $v = n - 1$, $\mathrm{sub}[v] > v$, $s \ne n$ →
Y. - $\mathrm{sub}[v] \ge v$ (and not case 2) →
N. - Champion $v$:
Yiff $\mathrm{pre}[v - 1] > \mathrm{pre}[\mathrm{sub}[v]]$.
E1 later reuses the same sweep but reads the numbers to count distinct sets.