Counting Paths in a Full Binary Tree

We consider an infinite full binary tree that is numbered in a heap‐style manner: the root is numbered \(1\); for any node numbered \(x\), its left child is \(2x\) and its right child is \(2x+1\). You are given two nodes \(a\) and \(b\). Note that in a tree there is a unique simple path (a path with no repeated vertices) between any two nodes. Let \(S\) be the sum of the labels along the unique path from \(a\) to \(b\) (including both endpoints). The task is to count how many simple paths in this binary tree have a sum of labels exactly equal to \(S\).

The interesting twist is that even though the simple path between \(a\) and \(b\) is unique, there might be many other simple paths (possibly consisting of one vertex only or spanning two different branches) that also sum to \(S\).

In fact, every simple path in a tree is uniquely determined by the pair of its endpoints. Note that a simple path may consist of a single vertex. For a given vertex \(w\) chosen as the lowest common ancestor (LCA) (or more generally, the highest vertex in the path), any simple path having \(w\) as the highest node can be decomposed into two downward paths starting from \(w\) (one or both of which can be trivial, i.e. empty, corresponding to the endpoint \(w\) itself). If one downward path yields a sum \(r\) (excluding \(w\)) and the other yields a sum \(s\) (excluding \(w\)), then the whole path has sum \(w + r + s\). For each vertex \(w\), downward paths are generated as follows. From \(w\), a move to the left child adds \(2w\) and a move to the right child adds \(2w+1\). In general, a downward path (of length \(k\ge1\)) starting at \(w\) produces a sum of \[ (2^{k+1}-2)\,w + t, \quad t \in [0,2^k-1]. \] Additionally, the empty path (staying at \(w\)) contributes a sum of 0. The problem is then to count, over all possible choices of a vertex \(w\) (which will serve as the "root" for the decomposition of a simple path), the number of unordered pairs of downward paths (allowing the possibility that one path is empty) such that \[ w + (\text{downward sum}_1 + \text{downward sum}_2) = S. \]

Your task is to compute \(S\) by first finding the unique simple path between \(a\) and \(b\), and then count the number of simple paths in the tree whose node labels sum to \(S\). You may assume that \(a\) and \(b\) are small enough so that \(S\) is moderate and only nodes with labels at most \(S\) need be considered.

inputFormat

The input consists of two space‐separated integers \(a\) and \(b\) representing two nodes in the tree.

outputFormat

Output a single integer: the number of simple paths in the tree whose sum of node labels equals \(S\), where \(S\) is the sum of labels on the unique path between \(a\) and \(b\).

sample

1 2

2