Figure 5

An illustration of Observation2. (a) A node u in a tree T, such that N(u) = {v ₁ ,v ₂ ,v ₃ }, and$\left|T_u^{v_1}\right|\le \left|T_u^{v_2}\right|\le \left|T_u^{v_3}\right|$. The subtree$T_u^{v_1}$ (bounded by a solid red line) contains$T_{v_2}^u$ and$T_{v_3}^u$ as subtrees (bounded by dashed and dotted blue lines, respectively), and therefore$\left|T_{v_2}^u\right|,\left|T_{v_3}^u\right|\le \left|T_u^{v_1}\right|\le \left|T_u^{v_2}\right|$. (b) The subtree$T_u^{v_2}$ (bounded by a solid red line) contains$T_{v_1}^u$ as a subtree (bounded by a dashed blue line), and therefore$\left|T_{v_1}^u\right|,\left|T_{v_2}^u\right|,\left|T_{v_3}^u\right|\le \left|T_u^{v_2}\right|$. (c) The DP matrix H. The rows of the matrix correspond to subtrees of T, sorted from top to bottom with non-decreasing tree size. Rows corresponding to subtrees of the form$T_u^{v_i}$ are in solid red, and rows corresponding to subtrees of the form$T_{v_i}^u$ are in waved-blue. All waved-blue rows have smaller indices than the row corresponding to$T_u^{v_2}$ (circled with a dashed green line).