【牛客小白月赛45】E - 筑巢（树形DP，dfs）

题目链接：E-筑巢_牛客小白月赛45 (nowcoder.com)

具体题意见原题。

思路

首先观察一下题目，这里的图是一棵树，有N - 1条边，说明整个图是一个连通图，每个点都直接相连或间接连通。

而且这里的边和点权值可以为负数，所以我们应该考虑，先更新叶子节点，再往上更新。

但是叶子节点不太好找，有关系吗？没有关系。

我们可以通过dfs，对树进行遍历，假如现在是节点x，下一个是p，那么就更新完p后更新节点x。在dfs拓展时记录下父节点，防止往回拓展。

既然是DP，那么就有状态转移方程：w[x] = max(w[x], w[x] + w[p] + d[x][p]);

最后遍历1 ~ N节点找出最大值即可，因为最大值并不一定是根节点，可能在中间断开了一下，导致最大值在树枝上。

代码

/* Copyright (C) 2022 ErikTse */
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <utility>
#include <stack>
#include <algorithm>
#define pb push_back
#define fi first
#define se second
#define pr printf
#define sc scanf
#define gc getchar
#define int long long//注意使用%lld输出long long类型数据
using namespace std;
inline int readInt(){//快速读入int
	int s = 0,w = 1;char c = gc();
	while(c > '9' || c < '0')w = (c == '-' ? -1 : 1),c = gc();
	while('0' <= c && c <= '9')s = s * 10 + c - '0',c = gc();
	return s * w;
}
inline string readString(){//快速读入string
	string s;char c = gc();
	while(c == ' ' || c == '\n' || c == '\r')c = gc();
	while(c != ' ' && c != '\n' && c != '\r')s += c,c = gc();
	return s;
}
/*-------全局变量------*/
const int maxn = 4e5 + 10,inf = 1e15;
int n;
struct Edge
{
	int x, w;//到x，舒适度为w 
};
vector<vector<Edge> > g;//邻接表
int w[maxn];
/*-----自定义函数------*/

inline void dfs(int f,int x)//f表示x的父节点
{
	for(auto i : g[x])
	{
		if(i.x == f)continue;//如果拓展的点是父节点跳过。
		dfs(x, i.x);//更新x的儿子
		w[x] = max(w[x],w[x] + w[i.x] + i.w);//儿子更新完成后更新x的舒适度
	}
}

signed main()
{
	//freopen("in.txt","r",stdin);
	n = readInt();
	g.resize(n + 1);
	for(int i = 1;i <= n; ++ i)w[i] = readInt();
	for(int i = 1;i <= n - 1; ++ i)
	{
		int x = readInt(), y = readInt(), v = readInt();
		g[x].pb({y,v});
		g[y].pb({x,v});
	}
	dfs(0, 1);
	pr("%lld\n",*max_element(w + 1, w + 1 + n));
	return 0;
}