B. Om Nom and Dark Park

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

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

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

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <string>
 7 #include <vector>
 8 #include <set>
 9 #include <map>
10 #include <stack>
11 #include <queue>
12 #include <sstream>
13 #include <iomanip>
14 using namespace std;
15 typedef long long ll;
16 const int INF=0x4fffffff;
17 const int EXP=1e-5;
18 const int MS=12;
19 
20 int num[1<<MS];
21 
22 int main()
23 {
24       int n;
25       memset(num,0,sizeof(num));
26       scanf("%d",&n);
27       for(int i=2;i<(1<<(n+1));i++)
28             scanf("%d",&num[i]);
29       int ans=0;
30       for(int i=(1<<n)-1;i>0;i--)
31       {
32             int lch=num[i<<1];
33             int rch=num[i<<1|1];
34             int t=max(lch,rch);
35             num[i]+=t;
36             ans+=2*t-lch-rch;
37       }
38       printf("%d
",ans);
39       return 0;
40 }