var
n,p,i,j,k:Longint;
a:array[0..105] of longint;
f,root:array[0..105,0..105] of longint;
procedure dfs(l,r:longint);
begin
if l>r then exit;
write(root[l,r],' '); dfs(l,root[l,r]-1); dfs(root[l,r]+1,r);
end;
begin
readln(n);
for i:=1 to n do read(a[i]);
for i:=1 to n do begin f[i,i-1]:=1; f[i,i]:=a[i]; root[i,i]:=i; end;
for p:=1 to n-1 do
for i:=1 to n-p do
begin
j:=i+p;
for k:=i to j do
if f[i,j]<f[i,k-1]*f[k+1,j]+a[k] then begin f[i,j]:=f[i,k-1]*f[k+1,j]+a[k]; root[i,j]:=k; end;
end;
writeln(f[1,n]); dfs(1,n);
end.

#include <iostream>
using namespace std;
int in[50];
int f[50][50];
int mr[50][50];
int dp(int s, int t)
{
int temp, rl, rr;
if(s > t) return 1;
if(s == t) return in[s];
if(f[s][t] != 0) return f[s][t];
for(int i = s; i <= t; ++i)
{
temp = f[s][t];
f[s][t] = max(f[s][t], dp(s, i-1) * dp(i+1, t) + in[i]);
if(f[s][t] > temp)
mr[s][t] = i;
}
return f[s][t];
}
void output(int s, int t)
{
if(s == t) {cout << s << ' '; return ;}
if(s > t) return ;
cout << mr[s][t] << ' ';
output(s, mr[s][t] - 1);
output(mr[s][t] + 1, t);
}
int main()
{
int n, ans=0, r;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >>in[i];

ans = dp(1, n);
cout << ans << endl;
output(1, n);
cout << endl;
return 0;
}

//P1100加分二叉树
#include <cstdio>
#include <cctype>
#include <cstring>

const int N = 35;

int value[N];//输入的每个节点的分数
int n;//节点数
int root[N][N];
//为了输出中序遍历,存下树 root[left][right] 表示点left, left + 1, left + 2... right - 1, right得到最优解时的父节点
int dp[N][N];
//dp[left][right]的最高分数,此题测试数据弱,不用long long也能过

inline int Read(){
int rtn = 0;
char tmp = getchar();
while (!isdigit(tmp)) tmp = getchar();
while (isdigit(tmp)){
rtn = rtn * 10 + tmp - '0';
tmp = getchar();
}
return rtn;
}

int dptree(int l, int r){
if (dp[l][r] != -1) return dp[l][r];
if (l > r)//树是空的
return 1;
if (l == r) return value[l];
int rtn = -1;
for (int i = l; i <= r; i++)//把所有可能出现的解都枚举一遍
if (rtn < dptree(l, i - 1) * dptree(i + 1, r) + value[i]){
rtn = dptree(l, i - 1) * dptree(i + 1, r) + value[i];
root[l][r] = i;
}
dp[l][r] = rtn;//存下答案
return rtn;
}

void midord(int l, int r){
if (l > r) return;
printf("%d ", root[l][r]);
midord(l, root[l][r] - 1);
midord(root[l][r] + 1, r);
}

int main(){
memset(root, -1, sizeof(root));
memset(dp, -1, sizeof(dp));
n = Read();
for (int i = 1; i <= n; i++){
value[i] = Read();
root[i][i] = i;
}
printf("%d\n", dptree(1, n));
midord(1, n);
putchar('\n');
return 0;
}

#include<stdio.h> //为什么不可以用 unsigned long int 或 long
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int n,value[50],f[50][50],path[50][50];
int search(int left,int right)
{
int mid,temp;
if(f[left][right]>0)
return f[left][right];
if(left>right)
{
f[left][right]=1;
}
else if(left==right)
{
f[left][right]=value[left];
path[left][right]=left;
}
else
{
for(mid=left;mid<=right;mid++)
{
temp=search(left,mid-1)* search(mid+1,right)+value[mid];
if(temp>f[left][right])
{
f[left][right]=temp;
path[left][right]=mid;
}
}
}
//cout<<"ok ";
return f[left][right];
}
void printTree(int left,int right)
{
int mid=path[left][right];
if(left>right)
return ;
cout<<(mid+1)<<" ";
printTree(left,mid-1);
printTree(mid+1,right);
}
void printhouTree(int left,int right)
{
int mid=path[left][right];
if(left>right)
return ;
cout<<(mid+1)<<" ";
printhouTree(mid+1,right);
printhouTree(left,mid-1);

}
int main()
{
cin>>n;
int i,j;
for(i=0;i<n;i++)
{
cin>>value[i];
for(j=0;j<n;j++)
{
f[i][j]=0;
path[i][j]=-1;
}
}
int sum;
sum=search(0,n-1);
cout<<sum<<endl;
printTree(0,n-1);
//cout<<endl;
//printhouTree(0,n-1);
return 0;
}

标准区间动态规划+搜索二分。

#include <cstdio>
#include <cstring>
#include <cstdlib>
long long a[50], dp[50][50];
int n, root[50][50];
void print(int left,int right){
     if (left>right) return;
     printf("%d ",root[left][right]);
     print(left, root[left][right]-1);
     print(root[left][right]+1, right);
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%I64d",&a[i]);
        dp[i][i]=a[i];
        root[i][i]=i;
    }
    for (int i=n;i>0;i--)
        for (int j=i+1;j<=n;j++)
            for (int k=i;k<=j;k++){ 
                if (dp[i][k-1]==0) dp[i][k-1]=1;
                if (dp[k+1][j]==0) dp[k+1][j]=1;
                if (dp[i][j] < (dp[i][k-1]*dp[k+1][j] + a[k])){
                     dp[i][j] = dp[i][k-1] *dp[k+1][j] + a[k];
                     root[i][j]=k;
                }
    }
    printf("%I64d\n",dp[1][n]);
    print(1,n);
    return 0;
}

裸的树形动规
附上喜闻乐见的Pascal代码：
var
d:array[1..30] of longint;
f:array[1..30,1..30] of int64;
root:array[1..30,1..30] of longint;
n,i:longint;
procedure dfs(l,r:longint);
var
i:longint;
s:int64;
begin
if f[l,r]>0 then exit;
dfs(l+1,r);
dfs(l,r-1);
if f[l+1,r]+d[l]>=f[l,r-1]+d[r] then
begin
f[l,r]:=f[l+1,r]+d[l];
root[l,r]:=l;
end
else
begin
f[l,r]:=f[l,r-1]+d[r];
root[l,r]:=r;
end;
for i:=l+1 to r-1 do
begin
dfs(l,i-1);dfs(i+1,r);
s:=f[l,i-1]*f[i+1,r]+d[i];
if s>f[l,r] then
begin
f[l,r]:=s;
root[l,r]:=i;
end;
end;
end;
procedure print(l,r:longint);
begin
write(root[l,r],' ');
if root[l,r]>l then
print(l,root[l,r]-1);
if root[l,r]<r then
print(root[l,r]+1,r);
end;
begin
readln(n);
for i:=1 to n do
read(d[i]);
for i:=1 to n do
begin
f[i,i]:=d[i];
root[i,i]:=i;
end;
dfs(1,n);
writeln(f[1,n]);
print(1,n);
end.

P1100加分二叉树
Accepted
记录信息
评测状态 Accepted
题目 P1100 加分二叉树
递交时间 2015-08-22 11:13:29
代码语言 C++
评测机 VijosEx
消耗时间 21 ms
消耗内存 532 KiB
评测时间 2015-08-22 11:13:40
评测结果

编译成功

foo.cpp: In function 'int main()':
foo.cpp:60:32: warning: unknown conversion type character 'l' in format [-Wformat=]
scanf( "%lld" , &p[i] );
^
foo.cpp:60:32: warning: too many arguments for format [-Wformat-extra-args]
foo.cpp: In function 'long long int dp(int, int)':
foo.cpp:37:26: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
rootrec[l][r] = root;
^

测试数据 #0: Accepted, time = 15 ms, mem = 532 KiB, score = 20

测试数据 #1: Accepted, time = 1 ms, mem = 528 KiB, score = 20

测试数据 #2: Accepted, time = 1 ms, mem = 532 KiB, score = 20

测试数据 #3: Accepted, time = 1 ms, mem = 528 KiB, score = 20

测试数据 #4: Accepted, time = 3 ms, mem = 528 KiB, score = 20

Accepted, time = 21 ms, mem = 532 KiB, score = 100
代码

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int n;
long long p[100 + 2];
long long f[30 + 2][30 + 2];
int rootrec[30 + 2][30 + 2];
int i;

long long dp( int l , int r )
{
if( l == r )
return p[l];
if( f[l][r] != -1 )
return f[l][r];
int i;
int root;
for( i = l + 1 ; i <= r - 1 ; i++ )
if( dp( l , i - 1 ) * dp( i + 1 , r ) + p[i] > f[l][r] )
{
f[l][r] = dp( l , i - 1 ) * dp( i + 1 , r ) + p[i];
root = i;
}
if( dp( l + 1 , r ) + p[l] > f[l][r] )
{
f[l][r] = dp( l + 1 , r ) + p[l];
root = l;
}
if( dp( l , r - 1 ) + p[r] > f[l][r] )
{
f[l][r] = dp( l , r - 1 ) + p[r];
root = r;
}
rootrec[l][r] = root;
return f[l][r];
}

void render( int l , int r )
{
if( l > r )
return;
if( l == r )
{
printf( "%d " , l );
return;
}
printf( "%d " , rootrec[l][r] );
render( l , rootrec[l][r] - 1 );
render( rootrec[l][r] + 1 , r );
return;
}

int main()
{
scanf( "%d" , &n );
for( i = 1 ; i <= n ; i++ )
scanf( "%lld" , &p[i] );
memset( f , -1 , sizeof( f ) );
cout << dp( 1 , n ) << endl;
render( 1 , n );
return 0;
}

为什么会有3ms！！！

记忆化搜索（实质是区间dp）+记录路径+递归输出
根据数据范围，应该用 unsigned long，我没留意只开了个 long，没想到也过了

#include <stdio.h>

int value[50];
int f[50][50]; //记录区间 left~right 可取得的最大值
int path[50][50]; //记录区间 left~right 取得最大值时选取的根节点编号

int search(int left, int right){
int mid, tmp;
if(f[left][right]>0)
return f[left][right];
if(left>right){
f[left][right] = 1;
}else if(left==right){
f[left][right] = value[left];
path[left][right] = left;
}else{
for(mid=left; mid<=right; mid++){
tmp = search(left, mid-1) * search(mid+1,right) + value[mid];
if(tmp>f[left][right]){
f[left][right] = tmp;
path[left][right] = mid;
}
}
}
return f[left][right];
}
void printTree(int left, int right){
int mid = path[left][right];
if(left>right)
return;
printf("%d ", mid+1); //由于我对节点采用从0开始编号的方式，所以输出时要+1
printTree(left, mid-1);
printTree(mid+1, right);
}
int main(){
int num, i, k;
scanf("%d", &num);
for(i=0; i<num; i++){
scanf("%d", &value[i]);
for(k=0; k<num; k++){
f[i][k] = 0;
path[i][k] = -1;
}
}
printf("%d\n", search(0, num-1));
printTree(0, num-1);
return 0;
}

#include <cstdio>
#include <cstring>
#define maxn 31
int solve(int L,int R);
void print(int L,int R);
int n,p[maxn],root[maxn][maxn],solution[maxn][maxn];
bool solved[maxn][maxn];
int solve(int L, int R)
{
if(solved[L][R]) return solution[L][R];
if(L>R) return 1;
solved[L][R]=true;
for(int i=L;i<=R;i++)
{
int x=solve(L,i-1)*solve(i+1,R)+p[i];
if(x>solution[L][R]){
root[L][R]=i;solution[L][R]=x;
}
}
return solution[L][R];
}
void print(int L, int R)
{
if(L>R) return;
printf("%d ",root[L][R]);
print(L,root[L][R]-1);
print(root[L][R]+1,R);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&p[i]);
memset(solved,false,sizeof(solved));
memset(solution,0,sizeof(solution));
memset(root,0,sizeof(root));
for(int i=1;i<=n;i++)
{
solved[i][i]=true;
solution[i][i]=p[i];
root[i][i]=i;
}
printf("%d\n",solve(1,n));
print(1,n);
return 0;
}

评测状态 Accepted
题目 P1100 加分二叉树
递交时间 2015-07-31 12:17:01
代码语言 C++
评测机 VijosEx
消耗时间 19 ms
消耗内存 548 KiB
评测时间 2015-07-31 12:17:04
评测结果
编译成功

foo.cpp: In function 'int main()':
foo.cpp:47:25: warning: unknown conversion type character 'l' in format [-Wformat=]
printf("%lld\n",f[1][n]);
^
foo.cpp:47:25: warning: too many arguments for format [-Wformat-extra-args]
foo.cpp:22:12: warning: unused variable 'ans' [-Wunused-variable]
long long ans=0;
^
测试数据 #0: Accepted, time = 0 ms, mem = 544 KiB, score = 20
测试数据 #1: Accepted, time = 18 ms, mem = 544 KiB, score = 20
测试数据 #2: Accepted, time = 0 ms, mem = 544 KiB, score = 20
测试数据 #3: Accepted, time = 0 ms, mem = 548 KiB, score = 20
测试数据 #4: Accepted, time = 1 ms, mem = 544 KiB, score = 20
Accepted, time = 19 ms, mem = 548 KiB, score = 100

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int a[40];
long long f[40][40];
int pre[40][40];
void print(int front,int back)
{
if(front>back)return;
if(front==back)
{
printf("%d ",front);
return;
}
printf("%d ",pre[front][back]);
print(front,pre[front][back]-1);
print(pre[front][back]+1,back);
}
int main()
{
long long ans=0;
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
f[i][i]=a[i];
f[i][i-1]=1;
}
for(int k=1;k<n;k++)
for(int i=1;i<=n-k;i++)
{
int front=i;
int back=i+k;
for(int j=front;j<=back;j++)
{
long long now=f[front][j-1]*f[j+1][back]+a[j];
if(f[front][back]<now)
{
pre[front][back]=j;
f[front][back]=now;
}
}
}
printf("%lld\n",f[1][n]);

print(1,n);
}

纯递归AC（用file数组记录已求过的a~b区间最大值，避免重复递归，就不会超时了）

#include<stdio.h>
int value[32]={0};
int root[32][32];
int bools[32][32];
int file[32][32];

int max(int c,int d)
{
if(c>d) return c;
else return d;
}

int r(int a,int b)
{
if(a==b) return value[a];
if(a>b) return 1;

int i,maxn=-1,x,x1,x2,x3;

for(i=a;i<=b;i++)
{
if(bools[a][i-1]==0) {x1=r(a,i-1);bools[a][i-1]=1;file[a][i-1]=x1;}
else x1=file[a][i-1];

if(bools[i+1][b]==0) {x2=r(i+1,b);bools[i+1][b]=1;file[i+1][b]=x2;}
else x2=file[i+1][b];

x3=value[i];

x=x1*x2+x3;

if(x>maxn) {maxn=x;root[a][b]=i;}
}

return maxn;
}

void printroot(int e,int f)
{
int y=root[e][f];

if(e==f) printf("%d ",e);
else if(e<f) {printf("%d ",y); printroot(e,y-1); printroot(y+1,f);}

}

int main( )
{

int i,j,max;
int n;
scanf("%d",&n);

for(i=0;i<=31;i++)
for(j=0;j<=31;j++)
{
root[i][j]=0;
bools[i][j]=0;
file[i][j]=0;
}

for(i=1;i<=n;i++)
scanf("%d",&value[i]);

max=r(1,n);

printf("%d\n",max);

printroot(1,n);

return 0;
}

*这是一道动态规划题。
*动态规划一定要注意边界值的初始化
*可能是我困了，第一次交时忘记把调试用的输入输出删掉。
*状态定义：f（i，j）表示【i，j】闭区间内的最大值。
*状态转移方程
f(i,j)=max{ f(i,k-1)*f(k+1,j)+value(k) };其中k从i到j变化。
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int value[33];
int size;
long long int f[33][33][2];
void init(){
int i, j, k;
for (i = 1; i <= size; i++){
f[i][i - 1][0] = 1;
}
for (i = size; i > 0; i--){
f[i][i][0] = value[i];
f[i][i][1] = i;
for (j = i + 1; j <= size; j++){
for (k = i; k <j; k++){
int temp = f[i][k - 1][0] * f[k + 1][j][0] + value[k];
if (temp>f[i][j][0]){
f[i][j][0] = temp;
f[i][j][1] = k;
}
}
}
}
}
void visit(int from, int to){
int m = f[from][to][1];
cout << m << " ";
if (m > from)
visit(from, m - 1);
if (m < to)
visit(m + 1, to);
}
int main(){
freopen("in.txt", "r", stdin);
cin >> size;
int i;
for (i = 1; i <= size; i++)cin >> value[i];
memset(f, 0, sizeof(f));
init();
cout << f[1][size][0] << endl;
visit(1, size);
return 0;
}

P1100加分二叉树
Accepted

记录信息

评测状态 Accepted
题目 P1100 加分二叉树
递交时间 2014-10-30 23:16:57
代码语言 C++
评测机 Jtwd2
消耗时间 0 ms
消耗内存 524 KiB
评测时间 2014-10-30 23:16:58

评测结果

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 524 KiB, score = 20

测试数据 #1: Accepted, time = 0 ms, mem = 524 KiB, score = 20

测试数据 #2: Accepted, time = 0 ms, mem = 524 KiB, score = 20

测试数据 #3: Accepted, time = 0 ms, mem = 516 KiB, score = 20

测试数据 #4: Accepted, time = 0 ms, mem = 520 KiB, score = 20

Accepted, time = 0 ms, mem = 524 KiB, score = 100

代码

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>

using namespace std;

int n;
long long sum;
int point[30 + 2];
int i;
int maxd;
long long f[30 + 2][30 + 2];
int g[30 + 2][30 + 2];
queue < int > q;

int ti;

long long dp( int l , int r )
{
if( l > r )
return 1;
if( l == r )
return point[l];
if( f[l][r] != -1 )
return f[l][r];
int j;
for( j = l ; j <= r ; j++ )
if( dp( l , j - 1 ) * dp( j + 1 , r ) + point[j] > f[l][r] )
{
f[l][r] = dp( l , j - 1 ) * dp( j + 1 , r ) + point[j];
g[l][r] = j;
}
return f[l][r];
}

void visit( int l , int r )
{
if( l == r )
{
q.push( l );
return;
}
if( g[l][r] != 0 )
{
q.push( g[l][r] );
visit( l , g[l][r] - 1 );
visit( g[l][r] + 1 , r );
}
return;
}

int max( long long a , long long b )
{
if( a > b )
return a;
return b;
}

int main()
{
memset( g , 0 , sizeof( g ) );
while( scanf( "%d" , &n ) != EOF )
{
ti = 0;
maxd = 0;
memset( point , 0 , sizeof( point ) );
for( i = 1 ; i <= n ; i++ )
scanf( "%d" , &point[i] );
for( i = 1 ; i <= n ; i++ )
{
memset( f , -1 , sizeof( f ) );
if( dp( 1 , i - 1 ) * dp( i + 1 , n ) + point[i] > maxd )
{
maxd = dp( 1 , i - 1 ) * dp( i + 1 , n ) + point[i];
ti = i;
}
}
q.push( ti );
visit( 1 , ti - 1 );
visit( ti + 1 , n );
cout << maxd << endl;
cout << q.front();
q.pop();
while( !q.empty() )
{
printf( " %d" , q.front() );
q.pop();
}
cout << endl;
}
return 0;
}

#include <cstdio>
#include <cstring>
#define INF 1044266559

int N,f[31][31],tree[31],way[31][31];

inline int max(int a,int b)
{
return a>b?a:b;
}

void TreeDP(int l,int r)
{
if (l>r) f[l][r]=1;
if (l==r) f[l][r]=tree[l],way[l][r]=l;
if (f[l][r]!=-INF) return;
for(int i=l,tmp;i<=r;i++)
{
TreeDP(l,i-1);
TreeDP(i+1,r);
tmp=f[l][i-1]*f[i+1][r]+tree[i];
if (tmp>f[l][r])
{
f[l][r]=tmp;
way[l][r]=i;
}
}
}

void print(int l,int r)
{
if (l>r) return;
printf("%d ",way[l][r]);
print(l,way[l][r]-1);
print(way[l][r]+1,r);
}

int main()
{
memset(f,-0x3f,sizeof(f));
scanf("%d",&N);
for(int i=1;i<=N;i++)
scanf("%d",tree+i);
TreeDP(1,N);
printf("%d\n",f[1][N]);
print(1,N);
return 0;
}

记忆化搜索
program pro;
var
a:array[0..100]of longint;
f:array[0..100,0..100]of int64;
g:array[0..100,0..100]of longint;
n,i,j,k:longint;

procedure treedp(l,r:longint);
var
ii:longint;
tmp:int64;
begin
if l>r then f[l,r]:=1;
if l=r then begin f[l,r]:=a[l]; g[l,r]:=l; exit; end;
if f[l,r]<>0 then exit;
for ii:=l to r do
begin
treedp(l,ii-1);
treedp(ii+1,r);
tmp:=a[ii]+f[l,ii-1]*f[ii+1,r];
if tmp>f[l,r] then
begin
f[l,r]:=tmp;
g[l,r]:=ii;
end;
end
end;

procedure print(l,r:longint);
begin
write(g[l,r],' ');
if l<=g[l,r]-1 then print(l,g[l,r]-1);
if r>=g[l,r]+1 then print(g[l,r]+1,r);
end;

begin
readln(n);
for i:=1 to n do read(a[i]);
treedp(1,n);
writeln(f[1,n]);
print(1,n);
end.

一遍A好高兴

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

long long int a[31], mem[31][31];
long long dp(int left, int right)
{

if ( left <= right){
if (mem[left][right] != 0) return mem[left][right];

long long ans = 1;
if (left == right) ans = a[left];
else for (int i = left; i <= right; i++)
ans = max(ans, dp(left, i-1)*dp(i+1, right) + a[i]);
mem[left][right] = ans;
return ans;
}
return 1;
}

void traceback(int l, int r)
{

if ( l < r)
{
for (int i = l; i <= r; i++)
if (dp(l, r) == dp(l, i-1)*dp(i+1, r) + a[i])
{ printf("%d ", i+1);
traceback(l, i-1);
traceback(i+1, r);
break;
}
}
else if (l == r) printf("%d ", l+1);
}

int main()
{ int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
memset(mem, 0, sizeof(mem));
printf("%lld\n", dp(0, n-1));
traceback(0, n-1);
printf("\n");
return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX = 31;

long long dp[MAX][MAX];
int pos[MAX][MAX];
int val[MAX];

long long dfs(int i, int j){
if(i > j)return 1;
else if(i == j)return val[i];
else if(dp[i][j])return dp[i][j];

int r = i;
for(; r <= j; ++r){
long long v = dfs(i, r - 1) * dfs(r + 1, j) + val[r];
if(v > dp[i][j]){
dp[i][j] = v;
pos[i][j] = r;
}
}
return dp[i][j];
}

void pre_order(int i, int j){
if(i > j)return;
else if(i == j){
printf("%d ", i + 1);
return;
}
printf("%d ", pos[i][j] + 1);
pre_order(i, pos[i][j] - 1);
pre_order(pos[i][j] + 1, j);
}

int main(int argc, char const *argv[]){
int n;

scanf("%d", &n);
for(int i = 0; i < n; ++i){
scanf("%d", &val[i]);
}

dfs(0, n - 1);

printf("%lld\n", dp[0][n - 1]);
pre_order(0, n - 1);
return 0;
}