admin 管理员组

文章数量: 887016

生命之树（树形dp，最大联通子块）

生命之树（树形dp，最大联通子块）


输入输出样例
示例
输入

5
1 -2 -3 4 5
4 2
3 1
1 2
2 5

输出

8

思路：分析：这道题是要我们在树中求一个最大连通块，我们可以定义f[i]为以i为根的子树中最大连通块的值，这样结果就是f[1~n]中的最大值，树形DP过程比较简单，一开始令f[i]=w[i]，也就是令这个连通块只包含自己这一个点，然后只要以子节点为根的子树中最大连通块的值大于0，就加上，按照这样进行dp就可以求出答案，细节参照代码：

原文链接

int dp[N] ;//dp[i]表示以i为根节点的子树中的最大连通块

void dfs(int u,int fa){dp[u]=a[u];for(int i=head[u];i;i=e[i].nxt){int to=e[i].to;if(to==fa)continue;dfs(to,u);dp[u]+=max((int)0,dp[to]);//注意啦是+=，
//        注意啦，max函数比较的俩个数类型要一致，主要是比较 某个具体数值和ll变量时}
}

long long类型的最小值用-0x3f3f3f3f,而不要 0xc0c0c0c0

  int res=-0x3f3f3f3f;    for(int i=1;i<=n;i++){res=max(res,dp[i]);}cout<<res;

#include <iostream>
using namespace std;
#define int long long int
int n;
const int N=1e5+5;
int a[N];
struct edge{int to,nxt;
}e[N<<1];
int head[N];
int cnt;
void add(int u,int v){e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
}
int dp[N];//dp[i]表示以i为根节点的子树中的最大连通块
void dfs(int u,int fa){dp[u]=a[u];for(int i=head[u];i;i=e[i].nxt){int to=e[i].to;if(to==fa)continue;dfs(to,u);dp[u]+=max((int)0,dp[to]);//注意啦是+=，
//        注意啦，max函数比较的俩个数类型要一致，主要是比较 某个具体数值和ll变量时}
}
signed main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}int u,v;for(int i=0;i<n-1;i++){cin>>u>>v;add(u,v);add(v,u);}dfs(1,0);//    cout<<dp[1];int res=-0x3f3f3f3f;    for(int i=1;i<=n;i++){res=max(res,dp[i]);}cout<<res;return 0;
}

本文标签： 生命之树（树形dp，最大联通子块）

版权声明：本文标题：生命之树（树形dp，最大联通子块） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732361787h1535422.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。