hdu 5524 Subtrees 递推

 二叉树如下：

              1

           /    

      2              3

     /             /  

  4       5      6      7

 /     /

8  9 10

从最后一个节点n开始沿着父节点往上爬，直到1（上图中就是：10->5->2->1）。

重要的一点：如果当前节点有兄弟节点（例如：10没有兄弟，5的兄弟是4），那么这个兄弟节点（例如：4）代表的子树一定是个满二叉树。

基于此思想开始往上爬。  :)

/*
Title :Subtrees
Status:AC
By wf,
*/
#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define FOR(i,s,t) for(int i = (s) ; i <= (t) ; ++i )

typedef long long ll;
typedef unsigned long long ull;
using namespace std;

const int inf=0x3f3f3f3f;
const int maxn=1e6+5;

ll n;
set<ll>s;

ll insertnum(ll rt){ 
    int c=0;
    while( rt<=n )
    {
        c++;
        s.insert( (1LL<<c)-1 );//把每一层的节点数加入集合
        rt=(rt<<1)+1;
    }

	return ( (1LL<<c)-1 );//返回rt节点代表子树拥有的节点数
}
void up(ll rt,ll num,ll step){

	s.insert(num);//把当前结点代表子树的节点数加入集合
	//printf("insert::%d
",num );
	if(rt==1)return;

	ll fa=rt/2;

	bool left=1;//当前结点为父节点的左孩子

	if(rt%2)left=0;

	ll other=0;
	if(left){
		other = rt+1;
	}else{
		other = rt-1;
	}

	ll othernum=0;
	if(other <= n) {
         othernum = insertnum(other);
	}

	up(fa,num+othernum+1,step+1 );
}
int main()
{
	//freopen("in.txt","r",stdin);
	while(scanf("%lld",&n)!=EOF){
		s.clear();
		up(n,1,1);
		printf("%d
",s.size() );
	}

	return 0;
}