发的多财经网
刷题记录:牛客NC202475树上子链
迪丽瓦拉
2024-04-10 13:52:08
0次

传送门:牛客

题目描述:

给定一棵树 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])

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

注意:此题还需要开longlong

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
ll dp[maxn];int n;
vectortree[101000];
ll a[maxn];ll ans=-inf;
void dfs(int u,int pre_u) {dp[u]=a[u];for(int i=0;iint v=tree[u][i];if(v==pre_u) continue;dfs(v,u);ans=max(dp[u]+dp[v],ans);dp[u]=max(dp[v]+a[u],dp[u]);}ans=max(dp[u],ans);return ;
}
int main() {n=read();for(int i=1;i<=n;i++) {a[i]=read();}int u,v;for(int i=1;i<=n-1;i++) {u=read();v=read();tree[u].push_back(v);tree[v].push_back(u);}dfs(1,-1);
//	ll ans=-inf;//三十分的惨痛教训
//	for(int i=1;i<=n;i++) {
//		ans=max(ans,dp[i]);
//	}cout<
词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：java-net-php-python-jsp班导师助理业务管理信息系统计算机毕业设计程序

下一篇：Python并发编程之进程间通信

相关内容

热门资讯

国信期货20230404：金银...
4月21日外汇交易提醒：美元下...
CWG资讯：美元周四连续第四个...
闫瑞祥：美指承压下跌，欧美支撑...
外汇交易提醒：美联储鸽派加息，...
闫瑞祥：美指关注昨低得失，欧美...
6月16日外汇交易提醒：美联储...
7月20日机构对金融市场观点汇...
田洪良：6月28日主要货币短线...
一张图：6月13日黄金白银、原...