F - Xor Minimizationの再帰関数が2^30でTLEしない理由

解法を見て、なぜ再帰関数でTLEしないのか疑問に思った。この再帰関数はDPみたいに状態をまとめているわけではないから、一番最下層(一番下の桁を見ているときを最下層と表す)まで行ったら、今再帰関数が見ている頂点的な区間は、その最下層の頂点的な区間ごとに今まで選んできた0,1は違うわけで、そうなったら最下層は2^30通りあると考えられるためそれを再帰関数で見たらTLEすると思った。
しかしここでNを見てみると10^5とある(1.5は省略)。これを最下層に当てはめてみると、 10^5を2^30個の区間に分けるの無理じゃね？ となる。だから最下層だとしても最大10^5個の区間を表す頂点しかなくて、それは上の階層でも最大10^5のため、マージソートのように計算量を考えると、O(層存在する頂点数)みたいに見積もれて、層は2^30なので30であり、存在する頂点はどの層でも最大10^5なのだから、O(3010^5)くらいに見積もれてTLEせずACできる。
なお、解説放送のACコードにおいてサイズが0だとしても掘るコードを書くとTLEする、そもそもmaxになりうる方を再帰関数で掘っていくので、サイズが0の方を掘るのは解法としておかしいのでWAになるのだが...