题目：黄金树（蓝桥OJ 4494）

问题描述：

 

---

解题思路：

        遍历到每一个点并计算每个点的黄金指数， 当该点的黄金指数为0时加到res，最后res就是答案。

        如何遍历：使用dfs。

        如何计算黄金指数：当为左儿子时key+1，右儿子key-1。

        如何实现树：定义一个结构体数组，内部存放左右儿子编号，另一种方式，定义x[i]、y[i]数组表示i节点的左右儿子编号。

        样例解释：蓝色表示黄金指数，红色表示权值。如下图所示：

---

 代码：        

#include
using namespace std;
struct tree{
	int l;int r;  // 左右儿子编号
  int w;  // 权值
}a[100009];  // 注意题目要求的n是1~1e5,不要开小
// 使用a记录i节点的左右儿子编号和权值**
 
int res = 0;  // 因为dfs内使用的res是全局变量，所以res会该改变**
void dfs(int x, int key){  // x:d当前节点 key当前节点黄金指数
	if(key == 0)res += a[x].w;
	if(a[x].l)dfs(a[x].l, key + 1);
	if(a[x].r)dfs(a[x].r, key - 1);
}
 
int main()
{
	int n;cin >> n;
	for(int i = 1; i <= n; i++)cin >> a[i].w;
	for(int i = 1; i <= n; i++){
		cin >> a[i].l >> a[i].r;
	}
	dfs(1, 0);
 
	cout << res << '\n';
	return 0;
 } 

---

知识点：树的实现，dfs