图论、二叉树

发现节点 $i$ 的父亲为 $\left\lfloor \dfrac{i}{2} \right\rfloor$，由于完全二叉树的高为 $\log n$ 级别，暴力跳父亲即可。

单组数据时间复杂度 $O(\log n)$。

#include<bits/stdc++.h>
using namespace std;
long long n,ans;
void solution(){
    scanf("%lld",&n);
    ans=0ll;
    while(n) ans+=n,n>>=1;
    printf("%lld\n",ans);
}
int T;
int main(){
    scanf("%d",&T);
    while(T--) solution();
    return 0;
}