和の木

$x_1,\ldots,x_n\in\mathbb{F}$（$n\ge1$）の和の木とは、葉がちょうど $n$ 枚あり、葉以外の頂点（内部頂点）がちょうど 2 つの子をもつ根つき木で、葉に $x_1,\ldots,x_n$ を 1 つずつ割り当てたものである。各頂点の値を、葉では割り当てた $x_i$、内部頂点では 2 つの子の値 $a,b$ から $\mathrm{fl}(a+b)$ と定め、根の値を木の計算結果という。葉 $i$ の深さ $d_i$ を、根から葉 $i$ までの道の上にある内部頂点の個数とし、$\max_id_i$ を木の高さという。