Subtrees

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 552 Accepted Submission(s): 265

Problem Description

There is a complete binary tree with N nodes.The subtree of the node i has Ai nodes.How many distinct numbers are there of Ai?

Input

There are multiple test cases, no more than 1000 cases.
For each case contains a single integer N on a line.

Output

The output of each case will be a single integer on a line:the number of subtrees that contain different nodes.

Sample Input

   5 6 7 8  

Sample Output

   3 4 3 5  

Source

BestCoder Round #61 (div.2)

思路：

问一棵完全二叉树有多少种子树包含的节点数量不同。

首先可以肯定的是，一棵完全二叉树有可能是满二叉树，满二叉树的子树依然是满二叉树。但是完全二叉树的子树有一棵是满二叉树，另一棵是完全二叉树。根据给定节点数量很轻易可以知道左右子树的形态，然后递归求解。n的数量太大要用long long。如果一棵完全二叉树是满二叉树，则其子树依然是满二叉树；如果完全二叉树不是满二叉树，则其中一棵子树是满二叉树，另一棵是完全二叉树。基于以上两点，可以根据结点的数量，进行递归求解。并且，对于一个满二叉树（完美二叉树），它的不同结点数等于它的最大深度；对于一个完全非满二叉树，它的不同结点数是它最大的完美二叉树的深度+一块非完美的树对整个树的贡献；因此我们只需要递归判断最大的完美二叉树然后计算非满部分对整体的贡献；因为深度是从0开始计算所以最后结果+1。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
typedef long long ll;

using namespace std;

ll ans,maxn,n;

int max(int i,int j)
{
    return (i>j)?i:j;
}

void find(ll x)
{
    ll l=x,r=x;
    ll dep=0;
    while(l*2<=n)
    {
        l*=2;
        dep++;
    }
    while(r*2+1<=n)
    r=r*2+1;
    if(l<=r) maxn=max(maxn,dep);//满二叉树------>这里if的条件是重点。如果if条件不是l<=r，而是r==n或者，(r-1)/2+1==l，都会超时。（我不知道为什么...）但是后来一想，这种情况还包括了叶子结点。因为所有的叶子结点有很多，如果都ans++的话会重复很多，所以这里就用l==r的时候代表叶子结点，并且处理时不会ans++而是在最后的时候统一+1代表加的这个是叶子结点。
    else
    {
        find(2*x);
        find(2*x+1);
        ans++;//如果不满的话，ans就会+1，所以ans是在统计不满的
    }
}
int main()
{
    while(cin>>n)
    {
        ans=0;
        maxn=0;
        find(1);
        cout<<ans+maxn+1<<endl;
    }
    return 0;
}

总体思路就是，先在整个树看是不是满二叉树，如果不是的话就把下行一层，在第二层的两个结点为根节点的两个子树中看是不是满二叉树。如果其中一个是二叉树，另一个不是二叉树，那么再去这个不是的二叉树中下行一层，再进行看是不是满二叉树。下层的满二叉树的deep+非满树对这棵子树的贡献=这个结点对应的子树的不同节点数。然后这个节点的结点数+这一层其他子树是满二叉树结点的deep=上一层的节点数，依此类推。

HDOJ 5524 Subtrees（二叉树）

Subtrees