1.题目描述：点击打开链接
2.解题思路：比赛时候这道题没有做出来，第二天早晨补题时才发现就是简单的DFS应用。题目要求出最少需要增加几盏路灯。假设我们已经知道了root的左子结点一共有suml盏路灯，右子结点一共有sumr盏路灯，，那么比较一下d[lson(root)]+suml和d[rson(root)]+sumr的大小即可。此时需要增加的路灯数量就是两者差的绝对值。同时返回较大的数即得到root的总路灯数量。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;#define lson(x) (x)<<1#define rson(x) ((x)<<1)+1#define N 12int d[1 << N];int n;int cnt;int dfs(int root)//返回root的路灯总数量{int l = 0, r = 0;if (d[lson(root)])l=dfs(lson(root));if (d[rson(root)])r=dfs(rson(root));if (!d[lson(root)] && !d[rson(root)])return 0;if (d[lson(root)] + l < d[rson(root)] + r){cnt += d[rson(root)] + r – d[lson(root)] – l;return d[rson(root)] + r;}else{cnt += d[lson(root)] + l – d[rson(root)] – r;return d[lson(root)] + l;}}void solve(){int root = 1;cnt = 0;dfs(root);cout << cnt << endl;}int main(){//freopen("t.txt", "r", stdin);while (~scanf("%d", &n)){int len = 1 << (n + 1);for (int i = 2; i < len; i++)scanf("%d", &d[i]);solve();}return 0;}
坚守自己的原则，世界上的诱-惑很多，
