树形dp模板

入门题目：

最大子树和、女仆咖啡厅桌游吧

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

int f[16001];int cnt[16001];int a[16001];
vector<int>e[16001];int n;int mx=-10000000;
void dfs(int n,int fa)
{
	f[n]=a[n];
	for(int i=0;i<e[n].size();i++)
	{
		if(e[n][i]!=fa)
		{
			dfs(e[n][i],n);
			if(f[e[n][i]]>0)
				f[n]+=f[e[n][i]];
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)
	{
		if(f[i]>mx)mx=f[i];
	}
	cout<<mx<<endl;
}

简单的dfs遍历，相当于线性dp中的1~n
dp方程设计在dfs的for循环中