acgo100pts洛谷36pts 求条
原题链接：41050.【树形动态规划】生命之树
2026-02-14 10:20:10
发布于：江苏
48阅读
0回复
0点赞
我也不知道哪有问题
#include<bits/stdc++.h>
using namespace std;
int n,a[105],dp[105];
vector<int>ad[105];
void dfs(int u,int fa)
{
dp[u]=a[u];
for(int v:ad[u])
{
if(v!=fa)
{
dfs(v,u);
dp[u]+=max(dp[v],0);
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<n;i++)
{
long long x,y;
cin>>x>>y;
ad[x].push_back(y);
ad[y].push_back(x);
}
dfs(1,0);
int m=0;
for(int i=1;i<=n;i++)
{
m=max(m,dp[i]);
}
cout<<m;
return 0;
}
有帮助，赞一个