题目：
主办方设计了一个获取食物的游戏，游戏的地图由N个方格组成，每个方格上至多2个传送门，通过传送门可将参与者传送至指定的其它方格。同时，每个方格上标注了三个数字：
- 第一个数字id:代表方格的编号，从0到 N-1，每个方格各不相同;
- 第二个数字parent-id: 代表从编号为parent-id的方格可以通过传送门传送到当前方格(-1则表示没有任何方格可以通过传送门传送到此方格，这样的方格在地图中有且仅有一个) ；
- 第三个数字value: 取值在[-100，100]的整数值，正整数代表与者得到相应数值单位的食物，负整数代表失去相应数值单位的食物(参与者可能存在临时持有食物为负数的情况)，0则代表无变化。
此外，地图设计时保证了参与者不可能到达相同的方格两次，并且至少有一个方格的value是正整数。游戏开始后，参与者任意选择一个方格作为出发点，当遇到下列情况之退出游戏。请计算参与者退出游戏后，最多可以获得多少单位的食物。
- 参与者当前所处的方格无传送门;
- 参与者在任意方格上主动宣布退出游戏
输入：
第一行: 方块个数N (N <10000)
接下来输入N行(id<Nparent-id < N,)，每行记录了相应方格上标注的3个数字，即id (0 <= id < 10000) 、parent-id (0 <= parent-id < 10000和value (-100<= value <= 100)，例如:3
0 -1 3
1 0 1
2 0 2
输出：
参与者最多可以获得的食物单位数，例如5，参与者从方格0出发，通过传送门到达方格2，一共可以获得3+25个单位食物，此时得到食物最多
样例：
输入:
7
0 1 8
1 -1 -2
2 1 9
4 0 -2
5 4 3
3 0 -3
6 2 -3
输出：9解释：参与者从方格0出发，通过传送门到达方格4，再通过传送门到达方格5，一共获得8+(-2) +3=9个单位食物，得到食物最多，或者与者在游戏开始时处于方格2，直接主动宣布退出游戏，也可以获得9个单位食物。
思路：
这题的本质显然是树搜索问题。建模后用深度优先搜索(DFS) 算法解决。难点在于如何建模。由题意可得，不会经过一个点两次则图中必然没有环，又由于只有一个节点的父亲节点为空（也即-1）， 则必然是一棵树。将dfs的含义定义为以从树的根节点能获得的最大的物品价值，在求解这个问题时会遍历所有树上的节点，相当于枚举了以任意节点为起点获得的最大值，因此在每个节点return前对最终答案进行更新即可。
代码：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;int dfs(int id, vector<vector<int>> &G, vector<int> &v, vector<int>&a) { //由于需要记录每一个节点向下的数据，按引用传递a以便修改int idMost = 0;for (int j : G[id]) {idMost = max(dfs(j, G, v, a), idMost);}a[id] = v[id] + idMost;return a[id];
}int main() {int N; //方块个数cin >> N;vector<vector<int>> G(N); //G[i]是编号为i的节点的子节点（i方块所能进入的方块）vector<int> v(N); //v[i]是第i个方块的valueint root; //记录作为根节点的方块编号for (int i = 0; i < N; i++) { int id, parent_id, value;cin >> id >> parent_id >> value;v[id] = value;if (parent_id == -1) { root = id; } //更新rootelse G[parent_id].push_back(id); //parent_id节点的所有子节点}vector<int> a(N); //f[i]表示以节点i为初始位置遍历时的最大路径加权dfs(root,G,v,a); //dfs搜索auto maxPosition = max_element(a.begin(), a.end()); // 返回的是最大值迭代器所在的位置cout << *maxPosition << endl;return 0;
}
简化为lamda函数形式：
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;int main() {int N; //方块个数cin >> N;vector<vector<int>> G(N); //G[i]是编号为i的节点的子节点（i方块所能进入的方块）vector<int> v(N); //v[i]是第i个方块的valueint root; //记录作为根节点的方块编号for (int i = 0; i < N; i++) { int id, parent_id, value;cin >> id >> parent_id >> value;v[id] = value;if (parent_id == -1) { root = id; } //更新rootelse G[parent_id].push_back(id); //parent_id节点的所有子节点}vector<int> a(N); //f[i]表示以节点i为初始位置遍历时的最大路径加权function<int(int)> dfs = [&](int i) {int valMore = 0;for (int j : G[i]) valMore = max(dfs(j), valMore);a[i] = v[i] + valMore;return a[i];};dfs(root); //dfs搜索，注意需要记录每一个节点向下的数据auto maxPosition = max_element(a.begin(), a.end()); // 返回的是最大值迭代器所在的位置cout << *maxPosition << endl;return 0;
}
