生命之树--树形dp

1.树形dp--在dfs遍历树的同时dp，从上到下递归，到叶子是边界条件

https://www.luogu.com.cn/problem/P8625

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
typedef pair<ll,int> pii;
int n,c;
ll w[N];
ll ma;
vector<int>  a[N];
ll dp[N];
void dfs(int u,int f)
{dp[u]=w[u];for(int v:a[u]){if(v!=f){	dfs(v,u);dp[u]+=max((ll)0,dp[v]);}}
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>w[i];for(int i=0;i<n-1;i++){int x,y;cin>>x>>y;a[x].push_back(y);a[y].push_back(x);}dfs(1,0);for(int i=1;i<=n;i++) ma=max(ma,dp[i]);cout<<ma;return 0;
}