结题报告--P5551洛谷--Chino的树学

题目：点此

                             题目描述

chino树是一棵具有某种性质的满二叉树，具体来说，对于这棵树的每一个非叶子节点，它的左子节点(a)(a)(a)的右子节点(c)(c)(c)与它的右子节点(b)(b)(b)的左子节点(d)(d)(d)的值相同，且ccc与ddd下方的子树也完全相同。现在，chino想知道，要如何从根节点走到其中任意叶节点使路上经过的节点的权值之和最大。

                               思路

先分析一下chino树（满二叉树）的性质（节点编号）。

k层的满二叉树的最后一个结点的编号是2^k-1，第一个叶子结点的编号是2^k-1，由此可知，判断节点是否为叶子：if(i>=pow(2,k-1)//i为结点编号                  判断此编号是否有对应节点：if(i>=0&&i<=pow(2,k)-1)//i为编号

定义一个变量n_1存储2^k-1,再定义一个变量x=n_1*2-1(就是2^k-1)。

本题难点之一就是把以深搜序列输入的树变成在数组里存储的树（数组存储是广搜序列），这个问题的解决方法是：在递归建树的函数里加一个参数now_number，表示现在是数组下标几了，因为数组下标是可以计算的：左子树下标：now_number*2，右子树下标：now_number*2+1。再加一个max_node_number,表示最大的结点编号，判断是否有左子树或右子树。

接下来就是判断最大值了。使用先根遍历遍历二叉树，由于这棵树是用数组存储的，所以里的in_oder函数的参数可以变为now_number，再加一个now_weight，表示现在的结点权值和。

这个函数里执行：先更新now_weight，把此节点权值加进去。然后判断此节点是否为叶子，若是则判断是否为最大值，若是则更新最大值，结束，不是叶子则按照继续遍历。

最后主函数就是这些函数的结合。

（犯的错误和收获全部丢失，无法叙述）

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 int tree[17000000];
 5 int read()
 6 {
 7     int s=0,w=1;
 8     char ch=getchar();
 9     while(ch<'0'||ch>'9')
10     {
11         if(ch=='-')
12             w=-1;
13         ch=getchar();
14     }
15     while(ch>='0'&&ch<='9')
16         s=s*10+ch-'0',ch=getchar();
17     return s*w;
18 }
19 
20 void maketree(int now_number,int max_node_number){
21     int now_node;
22     now_node=read();
23     tree[now_number]=now_node;
24     if(now_number*2>max_node_number){
25         return ;
26     }
27     maketree(now_number*2,max_node_number);
28     maketree(now_number*2+1,max_node_number);
29 }
30 int pow(int r){
31     if(r==1){
32         return 2;
33     }
34     int data=1;
35     if(r%2==1){
36         data=2;
37     }
38     int index=pow(r/2);
39     return index*index*data;
40 }
41 int maxx,n_1;
42 void pre_oder(int now_weight,int now_number){
43     now_weight+=tree[now_number];
44     if(now_number>=n_1){
45         if(now_weight>maxx){
46             maxx=now_weight;
47         }
48         return ;
49     }
50     pre_oder(now_weight,now_number*2);
51     pre_oder(now_weight,now_number*2+1);
52 }
53 int main(){
54     int n;
55     n=read();
56     n_1=pow(n-1);
57     int x=n_1*2-1;
58     maketree(1,x);
59     pre_oder(0,1);
60     cout << maxx;
61     return 0;
62 }