Hints: 01 Tree

In DFS leaf order, consider two distinct leaves that share the same parent.

They appear consecutively in the array $a$ (the DFS order visits one entire subtree of that parent before the other).

The parent is one edge closer to the root than either child. One child edge has weight $0$ and the other weight $1$, so the two leaf distances from the root differ by exactly $1$:

$$\left|a_{\text{left leaf's index}} - a_{\text{right leaf's index}}\right| = 1.$$

More specifically, the smaller of the two depths equals the parent’s distance from the root, and the larger equals that parent depth plus $1$.

Subproblem A (easy version). You are given only two numbers $x$ and $y$. Is there a parent whose two leaves have these distances?

Answer. You need $|x - y| = 1$. (And $x, y$ must be achievable in some tree, which the full process will enforce.)

Answer to Hint 1 (conceptual reverse process).

Take a complete binary tree and look at two sibling leaves in DFS order — they occupy two consecutive positions $i$ and $i + 1$.

If you delete those two leaves and merge their parent with the rest of the tree, the parent becomes a new leaf of the smaller tree.

The parent’s distance from the root is

$$\min(a_i, a_{i + 1})$$

(because from the parent you go down one more edge of weight $0$ or $1$ to reach the child; the shallow child determines the parent’s depth).

So a valid full tree can be thought of as building the leaf list from the outside in: repeatedly pick a pair of adjacent current leaves that could be siblings, merge them to a new leaf whose depth would be $\min$, and shorten the array.

The original problem asks only YES / NO, not the tree — so we only need a correct oblivious elimination order that matches this reverse process.

Question. Which adjacent pairs in the current list are even candidates to be siblings?

Answer to Hint 2. At any stage, a pair of sibling leaves must be adjacent among the surviving leaves.

So every merge removes one index from a doubleton neighborhood: each deleted leaf had (in the current list) at most one leaf to its left and at most one leaf to its right — and the sibling is one of those neighbors.

After many merges, “adjacent in the current list” is maintained if we simulate the list as a linked list (splice out deleted indices).

Question. If a leaf’s distance is $d$, and its only surviving neighbors have distances $u$ (left) and $v$ (right), what inequality must hold if this leaf is the deeper member of a sibling pair with one of those neighbors?

Answer to Hint 3.

Fix a step of the reverse process where the next merge removes the deeper leaf of a sibling pair (the algorithm always removes deeper leaves first — see Hint 5).

If the deeper leaf has depth $d$, the sibling leaf has depth $d - 1$, and the two must be adjacent in the current leaf list. So among the (at most two) surviving neighbors of that position, one of them has depth $d - 1$.

Therefore, if $m$ is the maximum depth among adjacent survivors,

$$m \ge d - 1 \quad\Longleftrightarrow\quad d \le m + 1.$$

That is exactly what model_sol.cpp tests with mx playing the role of $m$:

• compute mx from the left and right neighbor indices in the linked list (ignore a missing side),
• reject if a[i] > mx + 1.

Equivalent phrasing. When index $i$ is processed, we need some adjacent survivor with value a[i] - 1 available as the shallow side of the pair — and mx >= a[i] - 1 is the same inequality as a[i] <= mx + 1.

Extra constraint (a[i] == 0 && mx == 0). Two adjacent leaves cannot both have depth $0$: a parent has only one $0$-edge to its children. So if a[i] == 0 and every adjacent survivor also has depth $0$, the pair cannot be siblings and the instance is impossible.

Order of elimination.

Sort indices by decreasing a[i] and make a pass in that order. For each index i in that pass:

• i is still present in the linked list when it is visited — earlier iterations only splice other indices (those with strictly larger a), never i itself.
• Treat this step as: remove leaf i now as the deeper member of its sibling pair in some valid reverse-construction. Then splice i out.

Why largest depths first. Among leaves that are still alive, the deeper leaf in a sibling pair has strictly larger depth. Any valid backward merge deletes some deepest leaf of some sibling pair at that stage. So it is safe to commit to removing leaves from largest depth downward: if the current deepest remaining leaf already fails a[i] <= mx + 1, then at that moment no neighbor has depth a[i] - 1, so that leaf could never have been the deep side of a sibling pair — the whole test case is NO.

Why you cannot postpone a failing deepest leaf. Shallower leaves are processed later in the sorted order, so they are still in the list and still bound adjacency. Delaying the removal of a deep leaf does not create a new neighbor with the missing depth a[i] - 1; it only removes other indices that are not the needed sibling.

Implementation (matches model_sol.cpp).

• Build a doubly linked list on indices $0, \ldots, n - 1$: pr[i] = i-1, ne[i] = i+1 (with sentinels $-1$ and $n$).

• Sort indices order by decreasing a[i] (tie-break by index order as in iota — any tie-break works for correctness in practice; the reference uses stable relative order of equal $a$).

• For each i in order:

  • mx = -1 then if pr[i] != -1, mx = max(mx, a[pr[i]]); if ne[i] != n, mx = max(mx, a[ne[i]]).
  • If a[i] > mx + 1 or (a[i] == 0 and mx == 0): print NO and stop this test case.
  • Else splice i out: link pr[i] and ne[i] to each other.

• If all pass: print YES.

Time: $O(n \log n)$ per test case for sorting; splices are $O(1)$ each, total $O(n)$ besides sort. Memory $O(n)$.

Sanity checks on examples:

• 2 1 0 1 1 → YES (constructive example exists in the statement note).
• 1 0 2 1 3 → NO.

Work through NO by hand with the inequality: you will find an index whose depth is already too large compared to its current neighbors when it is processed in descending order.

Complete binary tree, every internal node has one $0$-edge and one $1$-edge to its children. DFS leaf order is left subtree completely, then right subtree.

Lemma 1 (sibling profile). Two sibling leaves occur at consecutive indices in $a$, and their values differ by $1$. The shallower value is the parent’s root distance.

Lemma 2 (reverse merging). Collapsing a sibling pair replaces the pair by their parent-as-leaf; in the new leaf list, adjacency reflects the shortened tree. Any valid original tree yields some sequence of such collapses ending in a single leaf.

Lemma 3 (local feasibility). Fix a reverse-construction step removing the deeper leaf of a sibling pair, when that leaf has depth $d$. Its sibling (depth $d - 1$) is one of the adjacent survivors. So if $m$ is the maximum depth among those neighbors, $m \ge d - 1$, equivalently $d \le m + 1$. Two adjacent zero depths cannot be siblings (a node has exactly one $0$-child edge), which is encoded as rejecting a[i] == 0 && mx == 0.

Scan indices in nonincreasing a[i]. The first index that violates the local test is impossible in any realization. If no index violates, the splices describe a valid order of pairwise collapses, hence a witness tree exists.

Sorting dominates: $O(n \log n)$ time, $O(n)$ memory, with $\sum n \le 2 \cdot 10^5$ over test cases.

Official discussion: Editorial for Hello 2024 (problem 1919D — 01 Tree).

The implementation in this folder (model_sol.cpp) follows Tourist’s submission: sort descending + doubly linked list + the two predicates a[i] > mx + 1 and (a[i] == 0 && mx == 0).