Start with the single-node tree \(T_1\). For each \(m\ge 2\), form \(T_m\) by making \(m\) the new root and reattaching the chain obtained from \(T_{m-1}\) by starting at the old root and repeatedly following the greatest child. Let \(S(n,k)\) be the sum of the labels on the unique path from node \(k\) to the root \(n\) in \(T_n\).
The implementation must evaluate this path sum for the very large input \((n,k)=\left(10^{17},9^{17}\right)\). The crucial observation is that the recursive tree rule has a direct binary description, so the tree never has to be built explicitly.
The recursive definition looks structural, but the actual parent relation turns out to depend only on powers of two. Once that relation is identified, the path from \(k\) to \(n\) becomes a simple process of clearing the leading bit of the remaining gap.
An induction on the recursive construction shows that, just before node \(m+1\) is inserted, the chain lifted from the old root is
$$m,\ m-1,\ m-3,\ m-7,\ \dots,\ m+1-2^j,$$
for every power \(2^j\le m\).
Equivalently, when a new root \(x\) is created, its direct children are exactly
$$x-1,\ x-2,\ x-4,\ x-8,\dots.$$
So the recursive tree is secretly organized by offsets that are powers of two.
A node \(y\) is attached to a later node \(x\) exactly when \(x-y\) is a power of two. Since later insertions may reattach \(y\) again, its parent in the final tree \(T_n\) is the largest such \(x\) with \(x\le n\).
Therefore, for every \(y<n\),
$$\operatorname{parent}_n(y)=y+2^{\lfloor \log_2(n-y)\rfloor}.$$
This is the key greedy rule: from the current node, move upward by the largest power of two that still fits in the remaining distance to \(n\).
Let \(x_0=k\), and define the remaining gap by
$$r_t=n-x_t.$$
Applying the parent formula gives
$$x_{t+1}=x_t+2^{\lfloor \log_2 r_t\rfloor}, \qquad r_{t+1}=r_t-2^{\lfloor \log_2 r_t\rfloor}.$$
Thus each step removes the most significant set bit of the current gap. When the gap becomes \(0\), the climb has reached \(n\).
Write the difference as
$$n-k=\sum_{i=1}^{s}2^{e_i}, \qquad e_1>e_2>\cdots>e_s\ge 0.$$
Because the algorithm removes one leading bit at a time, the visited nodes are exactly
$$x_j=k+\sum_{i=1}^{j}2^{e_i}\qquad (0\le j\le s),$$
where the empty sum for \(j=0\) is \(0\).
Therefore the path sum is
$$S(n,k)=\sum_{j=0}^{s}x_j=(s+1)k+\sum_{i=1}^{s}(s-i+1)2^{e_i}.$$
So the tree problem is equivalent to a weighted sum of the set bits of \(n-k\).
Take \((n,k)=(10,3)\). Then
$$n-k=7=2^2+2^1+2^0.$$
The remaining gaps are
$$7\to 3\to 1\to 0,$$
so the visited nodes are
$$3\to 7\to 9\to 10.$$
Hence
$$S(10,3)=3+7+9+10=29.$$
This matches the small checkpoint used by the implementation and shows concretely that each move clears one binary digit of the difference.
The C++, Python, and Java implementations all use the same fast loop. They keep the current node and the running sum, compute the largest power of two not exceeding the remaining gap \(n-\text{current}\), jump upward by that amount, and add the new node to the sum.
No explicit tree nodes, adjacency lists, or recursive traversal are needed for the real input. One implementation also includes tiny cross-checks on small values, confirming that the binary parent rule agrees with the recursive construction.
Let \(s\) be the number of \(1\)-bits in the binary expansion of \(n-k\). Each iteration removes exactly one of those bits, so the running time is \(O(s)\) and the memory usage is \(O(1)\). Since \(s\le \lfloor \log_2(n-k)\rfloor+1\), the method is also \(O(\log n)\) in the worst case.
Man beginnt mit dem Ein-Knoten-Baum \(T_1\). Für jedes \(m\ge 2\) entsteht \(T_m\), indem \(m\) zur neuen Wurzel gemacht wird und die Kette aus \(T_{m-1}\), die man von der alten Wurzel aus durch wiederholtes Folgen des größten Kindes erhält, direkt unter \(m\) umgehängt wird. Sei \(S(n,k)\) die Summe der Knotenwerte auf dem eindeutigen Pfad von \(k\) zur Wurzel \(n\) in \(T_n\).
Die Implementierung muss diese Pfadsumme für den sehr großen Eingabefall \((n,k)=\left(10^{17},9^{17}\right)\) berechnen. Die entscheidende Einsicht ist, dass sich die rekursive Baumregel in eine reine Binärbeschreibung übersetzen lässt, sodass der Baum nie explizit erzeugt werden muss.
Die Rekursion sieht zunächst strukturell aus, doch die Elternbeziehung hängt letztlich nur von Zweierpotenzen ab. Sobald diese Beziehung klar ist, wird der Aufstieg von \(k\) nach \(n\) zu einem Prozess, der in jeder Runde das führende gesetzte Bit der Restdifferenz entfernt.
Eine Induktion über die rekursive Konstruktion zeigt, dass unmittelbar vor dem Einfügen des Knotens \(m+1\) die von der alten Wurzel gelöste Kette die Form
$$m,\ m-1,\ m-3,\ m-7,\ \dots,\ m+1-2^j$$
hat, und zwar für jede Zweierpotenz \(2^j\le m\).
Äquivalent dazu hat eine neue Wurzel \(x\) als direkte Kinder genau die Knoten
$$x-1,\ x-2,\ x-4,\ x-8,\dots.$$
Damit steckt hinter der Rekursion in Wahrheit eine feste Struktur aus Zweierpotenz-Abständen.
Ein Knoten \(y\) wird genau dann unter einen späteren Knoten \(x\) gehängt, wenn \(x-y\) eine Zweierpotenz ist. Spätere Einfügungen können \(y\) erneut umhängen, daher ist sein Vater im endgültigen Baum \(T_n\) der größte solche Wert \(x\) mit \(x\le n\).
Also gilt für jedes \(y<n\)
$$\operatorname{parent}_n(y)=y+2^{\lfloor \log_2(n-y)\rfloor}.$$
Genau das ist die zentrale greedy-Regel: Vom aktuellen Knoten springt man um die größte Zweierpotenz nach oben, die noch in die Restlücke bis \(n\) passt.
Setze \(x_0=k\) und definiere die Restlücke durch
$$r_t=n-x_t.$$
Dann liefert die Elternformel
$$x_{t+1}=x_t+2^{\lfloor \log_2 r_t\rfloor}, \qquad r_{t+1}=r_t-2^{\lfloor \log_2 r_t\rfloor}.$$
Jeder Schritt entfernt also das höchstwertige gesetzte Bit der aktuellen Lücke. Sobald die Lücke \(0\) wird, ist \(n\) erreicht.
Schreibe die Differenz als
$$n-k=\sum_{i=1}^{s}2^{e_i}, \qquad e_1>e_2>\cdots>e_s\ge 0.$$
Da der Algorithmus immer genau ein führendes Bit entfernt, sind die besuchten Knoten genau
$$x_j=k+\sum_{i=1}^{j}2^{e_i}\qquad (0\le j\le s),$$
wobei die leere Summe für \(j=0\) gleich \(0\) ist.
Damit ergibt sich für die Pfadsumme
$$S(n,k)=\sum_{j=0}^{s}x_j=(s+1)k+\sum_{i=1}^{s}(s-i+1)2^{e_i}.$$
Die Baumaufgabe ist also äquivalent zu einer gewichteten Summe der gesetzten Bits von \(n-k\).
Nehmen wir \((n,k)=(10,3)\). Dann ist
$$n-k=7=2^2+2^1+2^0.$$
Die Restlücken verlaufen als
$$7\to 3\to 1\to 0,$$
also lautet der Pfad
$$3\to 7\to 9\to 10.$$
Folglich
$$S(10,3)=3+7+9+10=29.$$
Das stimmt mit dem kleinen Kontrollwert der Implementierung überein und zeigt anschaulich, dass jeder Sprung genau ein Binärbit der Differenz entfernt.
Die C++-, Python- und Java-Implementierungen verwenden alle dieselbe schnelle Schleife. Sie halten den aktuellen Knoten und die laufende Summe, bestimmen die größte Zweierpotenz, die die Restlücke \(n-\text{current}\) nicht überschreitet, springen um genau diesen Betrag nach oben und addieren den neuen Knoten zur Summe.
Für die eigentliche Eingabe sind weder explizite Baumknoten noch Adjazenzlisten noch rekursive Traversierungen nötig. Eine Implementierung enthält zusätzlich kleine Gegenprüfungen für winzige Werte, damit die bitbasierte Elternregel mit der rekursiven Konstruktion abgeglichen werden kann.
Sei \(s\) die Anzahl der Eins-Bits in der Binärdarstellung von \(n-k\). Jede Schleifenrunde entfernt genau eines dieser Bits, also beträgt die Laufzeit \(O(s)\) und der Speicherverbrauch \(O(1)\). Da \(s\le \lfloor \log_2(n-k)\rfloor+1\) gilt, ist das Verfahren im Worst Case auch \(O(\log n)\).
Başlangıçta tek düğümlü \(T_1\) ağacı vardır. Her \(m\ge 2\) için \(T_m\), \(m\) yeni kök yapılacak şekilde kurulur; eski kökten başlayıp her adımda en büyük çocuğu izleyerek elde edilen zincir koparılır ve doğrudan \(m\)'in altına bağlanır. \(S(n,k)\), \(T_n\) ağacında \(k\) düğümünden kök \(n\)'e giden tek yol üzerindeki etiketlerin toplamı olsun.
Uygulama bu toplamı çok büyük \((n,k)=\left(10^{17},9^{17}\right)\) girdisi için hesaplar. Kritik nokta, rekürsif ağaç tanımının doğrudan ikili sayı sistemiyle ifade edilebilmesidir; böylece ağacı açıkça kurmaya gerek kalmaz.
İlk bakışta yapı tamamen ağaç rekürsiyonu gibi görünür, fakat gerçek ebeveyn ilişkisi yalnızca iki kuvvetleriyle belirlenir. Bu ilişki ortaya çıkarılınca \(k\)'dan \(n\)'e tırmanış, kalan farkın en yüksek bitini her adımda silen basit bir sürece dönüşür.
Rekürsif kurulum üzerine yapılacak bir tümevarım, \(m+1\) düğümü eklenmeden hemen önce eski kökten alınan zincirin
$$m,\ m-1,\ m-3,\ m-7,\ \dots,\ m+1-2^j$$
şeklinde olduğunu gösterir; burada \(2^j\le m\) olan tüm iki kuvvetleri kullanılır.
Buna eşdeğer olarak, yeni kök \(x\)'in doğrudan çocukları tam olarak
$$x-1,\ x-2,\ x-4,\ x-8,\dots$$
olur. Yani rekürsif ağaç aslında iki kuvvetleri cinsinden sabit bir ofset düzeni taşır.
Bir \(y\) düğümü, ancak \(x-y\) bir iki kuvveti olduğunda daha büyük bir \(x\) düğümünün altına bağlanır. Daha sonraki eklemeler \(y\)'yi tekrar başka yere taşıyabildiğinden, nihai \(T_n\) ağacındaki ebeveyni \(x\le n\) koşulunu sağlayan en büyük böyle \(x\) olur.
Dolayısıyla her \(y<n\) için
$$\operatorname{parent}_n(y)=y+2^{\lfloor \log_2(n-y)\rfloor}.$$
Bu, çözümün greedy kuralıdır: mevcut düğümden \(n\)'e kalan mesafeye sığan en büyük iki kuvveti kadar yukarı zıpla.
\(x_0=k\) olsun ve kalan farkı
$$r_t=n-x_t$$
ile tanımlayalım. Ebeveyn formülü şu güncellemeyi verir:
$$x_{t+1}=x_t+2^{\lfloor \log_2 r_t\rfloor}, \qquad r_{t+1}=r_t-2^{\lfloor \log_2 r_t\rfloor}.$$
Böylece her adım, kalan farkın en yüksek değerli \(1\) bitini temizler. Fark \(0\) olduğunda \(n\)'e ulaşılmış olur.
Farkı
$$n-k=\sum_{i=1}^{s}2^{e_i}, \qquad e_1>e_2>\cdots>e_s\ge 0$$
şeklinde yazalım.
Algoritma her adımda bir lider biti kaldırdığı için ziyaret edilen düğümler tam olarak
$$x_j=k+\sum_{i=1}^{j}2^{e_i}\qquad (0\le j\le s)$$
olur; burada \(j=0\) için toplam boştur ve \(0\)'dır.
Buna göre yol toplamı
$$S(n,k)=\sum_{j=0}^{s}x_j=(s+1)k+\sum_{i=1}^{s}(s-i+1)2^{e_i}$$
şeklini alır. Yani soru, \(n-k\)'nin \(1\) bitlerinin ağırlıklı toplamına indirgenir.
\((n,k)=(10,3)\) alalım. Bu durumda
$$n-k=7=2^2+2^1+2^0.$$
Kalan farklar
$$7\to 3\to 1\to 0$$
şeklindedir; dolayısıyla ziyaret edilen düğümler
$$3\to 7\to 9\to 10$$
olur. Sonuç olarak
$$S(10,3)=3+7+9+10=29.$$
Bu değer uygulamadaki küçük kontrol örneğiyle aynıdır ve her sıçramanın farkın bir ikili basamağını sildiğini açıkça gösterir.
C++, Python ve Java uygulamalarının üçü de aynı hızlı döngüyü kullanır. Mevcut düğüm ve kısmi toplam tutulur; \(n-\text{current}\) farkını aşmayan en büyük iki kuvveti hesaplanır; bu kadar yukarı çıkılır ve yeni düğüm toplamın içine eklenir.
Gerçek girdi için açık ağaç düğümleri, komşuluk listeleri veya özyinelemeli dolaşım hiç gerekmez. Uygulamalardan biri ayrıca küçük değerlerde bu bit tabanlı ebeveyn kuralını rekürsif yapıyla karşılaştıran kısa doğrulamalar da içerir.
\(s\), \(n-k\)'nin ikili gösterimindeki \(1\) bit sayısı olsun. Her iterasyon bu bitlerden tam bir tanesini yok eder; dolayısıyla süre \(O(s)\), bellek ise \(O(1)\)'dir. Ayrıca \(s\le \lfloor \log_2(n-k)\rfloor+1\) olduğundan en kötü durumda yöntem \(O(\log n)\) olarak da ifade edilebilir.
Se empieza con el árbol \(T_1\), que contiene solo el nodo \(1\). Para cada \(m\ge 2\), el árbol \(T_m\) se obtiene haciendo de \(m\) la nueva raíz y recolgando debajo de ella la cadena que, en \(T_{m-1}\), se obtiene al comenzar en la antigua raíz y seguir siempre el hijo de mayor valor. Sea \(S(n,k)\) la suma de las etiquetas en el camino único desde \(k\) hasta la raíz \(n\) en \(T_n\).
La implementación debe calcular esta suma para la entrada enorme \((n,k)=\left(10^{17},9^{17}\right)\). La observación decisiva es que la regla recursiva del árbol tiene una descripción binaria directa, así que nunca hace falta construir el árbol completo.
A primera vista la definición es puramente estructural, pero la relación de parentesco final depende solo de potencias de dos. Una vez encontrada esa relación, el ascenso desde \(k\) hasta \(n\) se convierte en un proceso de borrar el bit más significativo de la diferencia restante.
Una inducción sobre la construcción recursiva muestra que, justo antes de insertar el nodo \(m+1\), la cadena extraída desde la antigua raíz es
$$m,\ m-1,\ m-3,\ m-7,\ \dots,\ m+1-2^j,$$
para toda potencia de dos \(2^j\le m\).
De manera equivalente, cuando aparece una nueva raíz \(x\), sus hijos directos son exactamente
$$x-1,\ x-2,\ x-4,\ x-8,\dots.$$
Por tanto, la estructura recursiva está gobernada en realidad por desplazamientos que son potencias de dos.
Un nodo \(y\) queda colgado de un nodo posterior \(x\) exactamente cuando \(x-y\) es una potencia de dos. Como inserciones aún más tardías pueden volver a recolgar \(y\), su padre en el árbol final \(T_n\) es el mayor de esos valores \(x\) con \(x\le n\).
Así, para todo \(y<n\),
$$\operatorname{parent}_n(y)=y+2^{\lfloor \log_2(n-y)\rfloor}.$$
Esa es la regla greedy esencial: desde el nodo actual se sube con la mayor potencia de dos que todavía cabe en la distancia que falta hasta \(n\).
Tomemos \(x_0=k\) y definamos la brecha restante por
$$r_t=n-x_t.$$
Aplicando la fórmula del padre se obtiene
$$x_{t+1}=x_t+2^{\lfloor \log_2 r_t\rfloor}, \qquad r_{t+1}=r_t-2^{\lfloor \log_2 r_t\rfloor}.$$
Cada paso elimina, por tanto, el bit más significativo encendido de la brecha actual. Cuando la brecha llega a \(0\), ya se alcanzó \(n\).
Escribamos
$$n-k=\sum_{i=1}^{s}2^{e_i}, \qquad e_1>e_2>\cdots>e_s\ge 0.$$
Como el algoritmo borra un bit líder en cada iteración, los nodos visitados son exactamente
$$x_j=k+\sum_{i=1}^{j}2^{e_i}\qquad (0\le j\le s),$$
donde la suma vacía para \(j=0\) vale \(0\).
Por consiguiente, la suma del camino es
$$S(n,k)=\sum_{j=0}^{s}x_j=(s+1)k+\sum_{i=1}^{s}(s-i+1)2^{e_i}.$$
La cuestión del árbol recursivo se transforma así en una suma ponderada de los bits encendidos de \(n-k\).
Tomemos \((n,k)=(10,3)\). Entonces
$$n-k=7=2^2+2^1+2^0.$$
Las brechas restantes son
$$7\to 3\to 1\to 0,$$
de modo que el camino es
$$3\to 7\to 9\to 10.$$
Por tanto,
$$S(10,3)=3+7+9+10=29.$$
Esto coincide con la pequeña comprobación usada por la implementación y muestra de forma concreta que cada salto elimina un dígito binario de la diferencia.
Las implementaciones en C++, Python y Java usan exactamente el mismo bucle rápido. Mantienen el nodo actual y la suma acumulada, calculan la mayor potencia de dos que no supera la brecha \(n-\text{current}\), suben esa cantidad y añaden el nuevo nodo a la suma.
Para la entrada real no hacen falta nodos explícitos, listas de adyacencia ni recorridos recursivos. Una de las implementaciones también contiene pequeñas verificaciones para valores muy reducidos, con el fin de confirmar que la regla binaria del padre coincide con la construcción recursiva.
Sea \(s\) el número de bits iguales a \(1\) en la expansión binaria de \(n-k\). Cada iteración elimina exactamente uno de esos bits, así que el tiempo es \(O(s)\) y la memoria es \(O(1)\). Como además \(s\le \lfloor \log_2(n-k)\rfloor+1\), el método también es \(O(\log n)\) en el peor caso.
先从只含一个节点的树 \(T_1\) 开始。对每个 \(m\ge 2\)，把 \(m\) 作为新根，并把 \(T_{m-1}\) 中从旧根出发、每一步都选择“编号最大的孩子”所得到的那条链整条摘下来，直接挂到 \(m\) 下面，于是得到 \(T_m\)。记 \(S(n,k)\) 为 \(T_n\) 中从节点 \(k\) 到根节点 \(n\) 的唯一简单路径上所有标签之和。
实现需要处理的实际输入是 \((n,k)=\left(10^{17},9^{17}\right)\)，规模极大，绝不可能真的把整棵树建出来。真正有效的做法，是把这条递归建树规则转写成一个只涉及二进制差值的父节点公式。
这道题表面上是树结构题，但核心并不在于维护树，而在于识别“谁会成为谁的父亲”。一旦父节点关系被写成闭式，路径求和就会退化成对 \(n-k\) 的二进制展开逐步清除最高位的过程。
对递归构造做归纳，可以得到一个非常整齐的结论：在插入节点 \(m+1\) 之前，从旧根被取出的那条链恰好是
$$m,\ m-1,\ m-3,\ m-7,\ \dots,\ m+1-2^j,$$
其中 \(2^j\le m\) 的所有二次幂都会出现。
把这个结论换一种说法就是：当新根 \(x\) 建立时，它的直接孩子正好是
$$x-1,\ x-2,\ x-4,\ x-8,\dots.$$
于是递归树并不是随意变化的结构，而是始终受“与根的差是二次幂”这一规则支配。
对于某个节点 \(y\)，当且仅当 \(x-y\) 是二次幂时，它会在插入 \(x\) 的那一步被挂到 \(x\) 下面。但以后如果又出现更大的这样的 \(x\)，它还会再次被改挂。因此在最终树 \(T_n\) 中，\(y\) 的父节点就是所有满足 \(x-y\) 为二次幂且 \(x\le n\) 的值中最大的那个。
因此，对任意 \(y<n\)，都有
$$\operatorname{parent}_n(y)=y+2^{\lfloor \log_2(n-y)\rfloor}.$$
这正是快速算法的贪心规则：从当前节点往上跳，跳的距离就是“不超过剩余距离 \(n-y\) 的最大二次幂”。
设起点 \(x_0=k\)，并把当前到根的剩余差值记为
$$r_t=n-x_t.$$
把上面的父节点公式代入，就得到
$$x_{t+1}=x_t+2^{\lfloor \log_2 r_t\rfloor}, \qquad r_{t+1}=r_t-2^{\lfloor \log_2 r_t\rfloor}.$$
也就是说，每一步都会删去当前剩余差值二进制表示里的最高位 \(1\)。当剩余差值变成 \(0\) 时，说明已经到达根 \(n\)。
把差值写成
$$n-k=\sum_{i=1}^{s}2^{e_i}, \qquad e_1>e_2>\cdots>e_s\ge 0.$$
由于算法每次删去一个最高位，所以访问到的节点依次就是
$$x_j=k+\sum_{i=1}^{j}2^{e_i}\qquad (0\le j\le s),$$
其中 \(j=0\) 时空和为 \(0\)。
于是路径和可以直接写成
$$S(n,k)=\sum_{j=0}^{s}x_j=(s+1)k+\sum_{i=1}^{s}(s-i+1)2^{e_i}.$$
这说明题目真正要求的，并不是复杂的树遍历，而是对 \(n-k\) 中所有置位比特做一次带权求和。
取 \((n,k)=(10,3)\)。这时
$$n-k=7=2^2+2^1+2^0.$$
剩余差值的变化为
$$7\to 3\to 1\to 0,$$
所以实际经过的节点是
$$3\to 7\to 9\to 10.$$
因此
$$S(10,3)=3+7+9+10=29.$$
这个结果与实现中的小规模校验完全一致，也直观展示了“每跳一次就删掉一个二进制最高位”到底是什么意思。
C++、Python 和 Java 三个实现使用的是同一个快速循环。它们维护当前节点和累计和，计算不超过剩余差值 \(n-\text{current}\) 的最大二次幂，向上跳这么远，然后把新到达的节点值加入总和。
对真实输入来说，完全不需要显式维护树节点、孩子列表或递归遍历。只有一个实现额外保留了非常小范围的交叉验证，用于确认这个二进制父节点规则和递归建树定义确实给出同一条祖先链。
设 \(s\) 为 \(n-k\) 的二进制表示中 \(1\) 的个数。每次循环恰好去掉其中一个 \(1\)，因此时间复杂度是 \(O(s)\)，空间复杂度是 \(O(1)\)。又因为 \(s\le \lfloor \log_2(n-k)\rfloor+1\)，所以最坏情况下也可以写成 \(O(\log n)\)。
Начинаем с дерева \(T_1\), состоящего из единственной вершины \(1\). Для каждого \(m\ge 2\) дерево \(T_m\) строится так: вершина \(m\) становится новым корнем, а цепочка, полученная в \(T_{m-1}\) из старого корня при последовательном выборе наибольшего ребенка, целиком перевешивается прямо под \(m\). Обозначим через \(S(n,k)\) сумму меток на единственном пути от вершины \(k\) к корню \(n\) в дереве \(T_n\).
Нужно вычислить эту сумму для очень большого входа \((n,k)=\left(10^{17},9^{17}\right)\). Главное наблюдение состоит в том, что рекурсивное правило построения дерева имеет прямую двоичную интерпретацию, поэтому реальное дерево строить не требуется.
На вид задача кажется чисто структурной, но окончательная функция родителя определяется только степенями двойки. Как только эта функция записана явно, подъем от \(k\) к \(n\) превращается в процесс последовательного удаления старшего установленного бита из оставшейся разности.
Индукция по рекурсивному построению показывает, что непосредственно перед вставкой вершины \(m+1\) от старого корня отделяется цепочка вида
$$m,\ m-1,\ m-3,\ m-7,\ \dots,\ m+1-2^j,$$
где берутся все степени двойки \(2^j\le m\).
Эквивалентно этому, у нового корня \(x\) прямыми детьми оказываются ровно вершины
$$x-1,\ x-2,\ x-4,\ x-8,\dots.$$
Значит, скрытая геометрия рекурсивного дерева полностью управляется сдвигами на степени двойки.
Вершина \(y\) подвешивается под более позднюю вершину \(x\) тогда и только тогда, когда \(x-y\) является степенью двойки. Поскольку еще более поздние вставки могут снова переподвесить \(y\), в конечном дереве \(T_n\) ее родителем будет максимальное такое \(x\), не превосходящее \(n\).
Следовательно, для любого \(y<n\)
$$\operatorname{parent}_n(y)=y+2^{\lfloor \log_2(n-y)\rfloor}.$$
Это и есть главный greedy-переход: из текущей вершины нужно подниматься на наибольшую степень двойки, которая еще помещается в оставшийся зазор до \(n\).
Пусть \(x_0=k\), а оставшаяся разность равна
$$r_t=n-x_t.$$
Тогда из формулы родителя сразу следует
$$x_{t+1}=x_t+2^{\lfloor \log_2 r_t\rfloor}, \qquad r_{t+1}=r_t-2^{\lfloor \log_2 r_t\rfloor}.$$
Иными словами, на каждом шаге удаляется старший установленный бит текущей разности. Когда разность становится равной \(0\), путь дошел до вершины \(n\).
Запишем
$$n-k=\sum_{i=1}^{s}2^{e_i}, \qquad e_1>e_2>\cdots>e_s\ge 0.$$
Так как алгоритм на каждом ходе убирает один ведущий бит, посещаемые вершины имеют вид
$$x_j=k+\sum_{i=1}^{j}2^{e_i}\qquad (0\le j\le s),$$
где при \(j=0\) пустая сумма равна \(0\).
Отсюда получаем формулу для суммы на пути:
$$S(n,k)=\sum_{j=0}^{s}x_j=(s+1)k+\sum_{i=1}^{s}(s-i+1)2^{e_i}.$$
Таким образом, задача о рекурсивном дереве сводится к взвешенной сумме единичных битов числа \(n-k\).
Возьмем \((n,k)=(10,3)\). Тогда
$$n-k=7=2^2+2^1+2^0.$$
Оставшиеся разности меняются так:
$$7\to 3\to 1\to 0,$$
поэтому путь состоит из вершин
$$3\to 7\to 9\to 10.$$
Следовательно,
$$S(10,3)=3+7+9+10=29.$$
Это совпадает с маленькой контрольной проверкой в реализации и хорошо показывает, что каждый переход уничтожает ровно один двоичный разряд разности.
Реализации на C++, Python и Java используют один и тот же быстрый цикл. Они хранят текущую вершину и накопленную сумму, находят наибольшую степень двойки, не превосходящую разность \(n-\text{current}\), переходят вверх на этот шаг и добавляют новую вершину к ответу.
Для реального ввода не нужны ни явные вершины дерева, ни списки детей, ни рекурсивный обход. В одной реализации присутствуют и маленькие перекрестные проверки на крошечных значениях, подтверждающие, что двоичное правило родителя полностью совпадает с рекурсивным определением дерева.
Пусть \(s\) обозначает число единичных битов в двоичной записи \(n-k\). Каждая итерация убирает ровно один такой бит, поэтому время работы равно \(O(s)\), а память составляет \(O(1)\). Так как \(s\le \lfloor \log_2(n-k)\rfloor+1\), в худшем случае это также \(O(\log n)\).
نبدأ بالشجرة \(T_1\) التي تحتوي على العقدة \(1\) فقط. ولكل \(m\ge 2\)، تُبنى الشجرة \(T_m\) بجعل \(m\) هو الجذر الجديد، ثم تؤخذ السلسلة التي نحصل عليها في \(T_{m-1}\) إذا بدأنا من الجذر القديم واتبعنا في كل مرة الابن الأكبر قيمة، وتُعلَّق هذه السلسلة مباشرة تحت \(m\). ولتكن \(S(n,k)\) هي مجموع القيم على المسار الوحيد من العقدة \(k\) إلى الجذر \(n\) في الشجرة \(T_n\).
المطلوب هو حساب هذا المجموع للحالة الكبيرة جدًا \((n,k)=\left(10^{17},9^{17}\right)\). الفكرة الحاسمة هي أن قاعدة بناء الشجرة تملك وصفًا ثنائيًا مباشرًا، ولذلك لا حاجة إلى بناء الشجرة كاملةً بشكل صريح.
تبدو المسألة في ظاهرها مسألة بنية شجرية تكرارية، لكن علاقة الأبوة النهائية تعتمد فقط على قوى العدد \(2\). وما إن تُكتب هذه العلاقة بصيغة مباشرة حتى يصبح الصعود من \(k\) إلى \(n\) مجرد عملية حذف للبت الأعلى من الفارق المتبقي في كل خطوة.
باستقراء البناء التكراري يتبين أنه قبل إدراج العقدة \(m+1\) مباشرة، تكون السلسلة المأخوذة من الجذر القديم هي
$$m,\ m-1,\ m-3,\ m-7,\ \dots,\ m+1-2^j,$$
وذلك لكل قوة للعدد \(2\) تحقق \(2^j\le m\).
وبصياغة مكافئة، فإن الجذر الجديد \(x\) تكون له أبناء مباشرون هم بالضبط
$$x-1,\ x-2,\ x-4,\ x-8,\dots.$$
إذن البنية التكرارية مخفية داخل نمط بسيط تحكمه فروق تساوي قوى للعدد \(2\).
ترتبط العقدة \(y\) بعقدة لاحقة \(x\) إذا وفقط إذا كان \(x-y\) قوة للعدد \(2\). وبما أن إدراجات أحدث قد تعيد ربط \(y\) مرة أخرى، فإن أباها في الشجرة النهائية \(T_n\) هو أكبر قيمة من هذا النوع لا تتجاوز \(n\).
ولذلك، لكل \(y<n\)، لدينا
$$\operatorname{parent}_n(y)=y+2^{\lfloor \log_2(n-y)\rfloor}.$$
وهذه هي القاعدة الجشعة الأساسية: من العقدة الحالية نصعد بمقدار أكبر قوة للعدد \(2\) لا تزال ضمن المسافة المتبقية حتى \(n\).
لنأخذ \(x_0=k\)، ولنعرّف الفارق المتبقي بـ
$$r_t=n-x_t.$$
عندها تعطي صيغة الأب التحديث التالي:
$$x_{t+1}=x_t+2^{\lfloor \log_2 r_t\rfloor}, \qquad r_{t+1}=r_t-2^{\lfloor \log_2 r_t\rfloor}.$$
أي أن كل خطوة تمحو أعلى بت مضبوط في الفارق الحالي. وعندما يصبح الفارق \(0\)، نكون قد وصلنا إلى \(n\).
لنكتب الفرق على الصورة
$$n-k=\sum_{i=1}^{s}2^{e_i}, \qquad e_1>e_2>\cdots>e_s\ge 0.$$
وبما أن الخوارزمية تحذف في كل مرة بتًا قياديًا واحدًا، فإن العقد المزارة هي تمامًا
$$x_j=k+\sum_{i=1}^{j}2^{e_i}\qquad (0\le j\le s),$$
حيث تكون المجموعة الفارغة عند \(j=0\) مساوية لـ \(0\).
ومن ثم فإن مجموع المسار يساوي
$$S(n,k)=\sum_{j=0}^{s}x_j=(s+1)k+\sum_{i=1}^{s}(s-i+1)2^{e_i}.$$
وهكذا تتحول مسألة الشجرة التكرارية إلى مجموع موزون للبتات المساوية لـ \(1\) في العدد \(n-k\).
خذ \((n,k)=(10,3)\). عندئذ
$$n-k=7=2^2+2^1+2^0.$$
ويتغير الفارق المتبقي وفق
$$7\to 3\to 1\to 0,$$
لذلك يكون المسار
$$3\to 7\to 9\to 10.$$
ومن ثم
$$S(10,3)=3+7+9+10=29.$$
وهذا يطابق نقطة الفحص الصغيرة المستخدمة في التنفيذ، ويُظهر بوضوح أن كل قفزة تزيل رقمًا ثنائيًا واحدًا من الفرق.
تنفذ تطبيقات C++ وPython وJava الحلقة السريعة نفسها. فهي تحتفظ بالعقدة الحالية وبالمجموع الجاري، ثم تحسب أكبر قوة للعدد \(2\) لا تتجاوز الفارق \(n-\text{current}\)، وتصعد بهذا المقدار، ثم تضيف العقدة الجديدة إلى المجموع.
لا حاجة مع المدخل الحقيقي إلى عقد شجرية صريحة أو قوائم أبناء أو اجتياز تكراري. كما أن أحد التطبيقات يتضمن اختبارات صغيرة جدًا للمقارنة بين هذه القاعدة الثنائية وبين البناء التكراري نفسه.
ليكن \(s\) هو عدد البتات التي تساوي \(1\) في التمثيل الثنائي للعدد \(n-k\). كل دورة تحذف بتًا واحدًا بالضبط، ولذلك يكون الزمن \(O(s)\) والذاكرة \(O(1)\). وبما أن \(s\le \lfloor \log_2(n-k)\rfloor+1\)، فيمكن أيضًا كتابة التعقيد في أسوأ حالة على صورة \(O(\log n)\).