test8开始WA,代码感觉无问题捏
#include <bits/stdc++.h>
using namespace std;
const int N = 510000;
typedef struct NumTree
{
int value;
int left;
int right;
} NumTree;
NumTree numtrees[N];
int loc[N];
int DFS(NumTree numtrees[], int idx, int value) // 深搜
{
if (value == 0)
return 0;
if (loc[idx] != 0)
return loc[idx];
int leftn = value + DFS(numtrees, numtrees[idx].left, numtrees[numtrees[idx].left].value);
int rightn = value + DFS(numtrees, numtrees[idx].right, numtrees[numtrees[idx].right].value);
return loc[idx] = leftn > rightn ? leftn : rightn;
}
int main()
{
int r;
while (cin >> r)
{
string line;
int idx = 0;
getline(cin, line);
memset(loc, 0, sizeof(loc));
memset(numtrees, 0, sizeof(numtrees)); // 值全部置为0,防止树高度小于上一树时出错
for (int i = 0; i < r; i++) // 搭建整个树
{
getline(cin, line);
istringstream iss(line);
while (iss >> numtrees[idx].value)
{
numtrees[idx].left = idx + 1 + i;
numtrees[idx].right = idx + 2 + i;
idx++;
}
}
cout << DFS(numtrees, 0, numtrees[0].value) << endl;
}
}