当前位置：首页 > article >正文

#Z1890. 裁枝剪叶

article 2025/3/1 23:09:31

题目

思路

做这道题之前可以先看看：#B. 部落联盟_草原上有n个部落,每个部落都有其坐标(xi,yi) 每个部落都有个武力值,可正可负由于-CSDN博客

我们可以这么做:

设以x节点为根的子树的点权和最大值为dp[x]

那么在dfs遍历树的节点时

先将dp[x]设为x的点权

然后每枚举完x的一个儿子点后判断如果dp[son] > 0,则dp[x]+=dp[son]

否则dp[x]就不用动。

最后取dp[1~n]的最大值就行了

~~是不是觉得恍然大悟~~

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,u,v,d[100001],ans = -114514191810,dp[100001];
vector<int> vec[1000001];
void dfs(int x,int fa)
{
  dp[x] = d[x];
  for(int i = 0;i < vec[x].size();i++)
    if(fa != vec[x][i])
    {
      dfs(vec[x][i],x);
      if(dp[vec[x][i]] > 0) dp[x] += dp[vec[x][i]];
    }
}
signed main()
{
  cin>>n;
  for(int i = 1;i <= n;i++) cin>>d[i];
  for(int i = 1;i < n;i++)
  {
    cin>>u>>v;
	  vec[u].push_back(v);
	  vec[v].push_back(u);
  }
  dfs(1,0);
  for(int i = 1;i <= n;i++) ans = max(ans,dp[i]);
  cout<<ans;
  return 0;
}