传送门:牛客

题目描述:

给定一棵树 T ，树 T 上每个点都有一个权值。
定义一颗树的子链的大小为：这个子链上所有结点的权值和 。
请在树 T 中找出一条最大的子链并输出。
输入:
5
2 -1 -1 -2 3
1 2
2 3
2 4
2 5
输出:
4

一道简单的树形dp的题目,但是有一些需要注意的点

主要思路:

1. 首先这个dp方程还是比较好想的,只要维护一个dp[u]来记录以u为根的树链的最大权值和dp[u]来记录以u为根的树链的最大权值和dp[u]来记录以u为根的树链的最大权值和,那么对于我们的转移方程来说就是直接枚举uuu的每一个儿子vvv,然后找一个最大的权值就行

dp[u]=max(d[v]+a[u],dp[u])dp[u]=max(d[v]+a[u],dp[u])dp[u]=max(d[v]+a[u],dp[u])

2. 但是需要注意的是,我们的子链是一整条链,也就是说我们的最终的答案并不是在dp[i]dp[i]dp[i]取一个最大值,而是需要一个节点的两个子树和(想一下一个节点加上两个子树也还是一个链!!!),当时我始终没想到这一点,然后一直303030分,真是醉了

注意:此题还需要开longlong

#include 
#include 
#include 
#include 
#include 
#include