最大子树和(树形dp）

本文主要是介绍最大子树和(树形dp），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

传送门

树形dp入门题，先放代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
struct Edge{
	int v, w, next;
}edge[N];
int tot, head[N], maxn = -2147483647, f[N], value[N];

void add(int u, int v){
	edge[tot].v = v;
	edge[tot].next = head[u];
	head[u] = tot ++;
}

void dfs(int now, int pre){
	f[now] = value[now];
	for(int i = head[now]; i != -1; i = edge[i].next){
		int v = edge[i].v;
		if(v == pre)
			continue;
		dfs(v, now);
		if(f[v] > 0)
			f[now] += f[v]; 
	}
}
int main(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++)
		cin >> value[i];
	memset(head, -1, sizeof head);
	for(int i = 1; i < n; i ++){
		int a, b;
		cin >> a >> b;
		add(a, b);
		add(b, a);
	}
	dfs(1, 0);	
	for(int i = 1; i <= n; i ++)
		maxn = max(maxn, f[i]);
	cout << maxn << endl;
	return 0;
}

这篇关于最大子树和(树形dp）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！