【牛客小白月赛45】E – 筑巢(树形DP,dfs)

发布于 2022-03-05  909 次阅读


题目链接: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;
}

19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-07-09