B. Om Nom and Dark Park

在满二叉树上的某些边上添加一些值。使得根节点到叶子节点的路径上的权值和都相等。求最少需要添加多少。

我们利用性质解题。考察兄弟节点。由于他们从跟节点到父节点这路径是相同的，所以需要添加的值为 2*max(lch,rch)-lch-rch; 同时将max(lch,rch)累加到父节点。

思路是最重要的。有时候不是聪不聪明的问题，而是会不会思考的问题。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <string>

 #include <vector>

 #include <set>

 #include <map>

 #include <stack>

 #include <queue>

 #include <sstream>

 #include <iomanip>

 using namespace std;

 typedef long long ll;

 const int INF=0x4fffffff;

 const int EXP=1e-;

 const int MS=;

 int num[<<MS];

 int main()

 {

       int n;

       memset(num,,sizeof(num));

       scanf("%d",&n);

       for(int i=;i<(<<(n+));i++)

             scanf("%d",&num[i]);

       int ans=;

       for(int i=(<<n)-;i>;i--)

       {

             int lch=num[i<<];

             int rch=num[i<<|];

             int t=max(lch,rch);

             num[i]+=t;

             ans+=*t-lch-rch;

       }

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

       return ;

 }

秒客网

B. Om Nom and Dark Park

相关文章