So how to prove that important conclusion in the edtorial of 2127D?
I mean this part:
Now, we only need to arrange the leaves adjacent to each vertex relative to each other. Because their positions relative to the other vertices depend only on the four ways to arrange the main path. The proof of that is boring, so we won’t bore you with it :)
What is it?
Auto comment: topic has been updated by esc_qwq (previous revision, new revision, compare).
You cannot place a nonleaf between two other nodes. Suppose node 1 is connected to some vertices, say 2, 3, and 4, and node 2 is a nonleaf (it is connected to node 5). Then suppose you place 2 in the middle; WLOG you arrange it as 3 2 4. Now there's nowhere to place node 5. If you put it to the left of node 1, then edge 13 crosses edge 25. But if you put it to the right of node 1, then edge 14 crosses edge 25. Therefore, nonleaves cannot be in between other nodes, so it suffices to arrange the leaves amongst themselves, then place them in between the nonleaves.
(The case where there is only one nonleaf is also fixed. Consider the same case as before, and say nodes 3 and 4 are leaves. Suppose WLOG we place node 5 to the left of node 1. Then node 2 must be to the left of nodes 3 and 4, by similar reasoning.)
Got it, Thank you very much!