蓝桥杯生命之树（DP）
输入：5
1 -2 -3 4 5
4 2
3 1
1 2
2 5
输出：8思路：
无向无环图的存储，且节点编号从1 开始（遍历注意一下）。本题是求这颗树中相互连接的节点的和最大问题，也就是连通块和最大问题，用dfs遍历图，dp[x]表示以节点x为跟的部分的和，如果dp[v[x][i]]小于0，那么不会增大dp[x]的值，所以舍去，如果dp[[x][i]]>0，则dp[x]+=dp[[x][i]]，最后在比较各部分的dp，找到最大值即为所求。
注意：0ll是表示长整型的0，max比较一般要同类型
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,a[N],dp[N];
vector<int> v[N];
void dfs(int x,int fa)
{
dp[x]=a[x];
for(int i=0;i<v[x].size();i++)
{
if(v[x][i]==fa) continue;
dfs(v[x][i],x);
dp[x]+=max(0ll,dp[v[x][i]]);//不能确定dp什么时候<0,因此要递归遍历
}
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=0;i<n-1;i++)
{
int a,b;
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
dfs(1,-1);
int ans=-0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
ans=max(ans,dp[i]);
}
cout<<ans<<endl;
}