[数据结构与算法]dia和威严（dfs）

（1）代码 + 思路（注释）

// 边 权值 树 DFS
// 边权，点权 
// 因为只会往下，所以不开标记数组（不会回溯） 
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
#define ll long long 
vector<pair<int, int>> resu[N]; // 存储上级x到下级y传递信息的时间k

int n; // 学生会的总人数，包括会长dia（root）

int und[N]; // 存储2 - n好学生的理解信息的时间
int maxTime; //最大总时间花费 在过程中维护更新这个值 

// x 代表当前到的结点
// tmp 表示到了当前点的边传递信息(k)花费总时间之和 
void dfs(int x, int tmp) {
	maxTime = max(maxTime, tmp + und[x]); // und[x] 当前到的这个点x -- 信息接收者理解信息的时间
	
	// 遍历当前点的每一条边（每一个下级） 
	for (int i = 0; i < resu[x].size(); ++i) {
		dfs(resu[x][i].first, tmp + resu[x][i].second); // first y，second k 
	}
}
int main() {
	cin >> n;
	// 存储每个学生的理解信息的时间 
	for (int i = 2; i <= n; ++i) {
		cin >> und[i];
	}
	
	// 存储边（点到点传递信息的时间）
	// n - 1 行 
	for (int i = 2; i <= n; ++i) {
		int x, y, k;
		cin >> x >> y >> k;
		resu[x].push_back({y, k}); // 就像图的存储（x, y），边上有值(k) 
	}
	
	// 从根节点 会长开始，一开始边传递信息时间总合为0 
	dfs(1, 0);
	cout << maxTime << endl; 
	return 0;
} 

（2）测试数据

3
3 4
1 2 4
1 3 2

与50位技术专家面对面

20年技术见证，附赠技术全景图