【学习笔记】子树和

定义

在数据结构中存在一种叫“树”的结构。

树的定义：树是由$n$个节点（或元素）组成的有限集合（记为$T$）。

• 如果$n=0$，它是一棵空树。

• 如果$n>0$，这个n个节点有且仅有一个节点作为树的根节点，简称为跟，其余节点可分为$m(m\leq 0)$个互不相干的有限集合$T1,T2\cdots$，其中，每个自己不呢神是一棵符合定义的树，成为根节点的子树。

求二叉树的最大子树和

p_lnk

通过递归树形dp，求以$u$为根的最大值。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100010;
vector <int> g[MAXN];
typedef long long ll;
ll w[MAXN],dp[MAXN];
int n;
void dfs(int u,int fa)
{
	dp[u]=w[u];
	for(auto v:g[u])
	{
		if(v==fa)continue;
		dfs(v,u);
		dp[u]+=max(dp[v],0LL);
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>w[i];
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0);
	cout<<*max_element(dp+1,dp+n+1);
	return 0;
}