苏州建设网站免费网站制作软件平台

有了上一篇博客，没有看上一篇博客的可以看看上一篇博客，我们对没有上司的舞会这道题会有更好的理解~

所以关键的思路就是确定对于每一个节点我们应该维护什么内容才是最合适的，这个题目和上一篇博客的最后一道题目很相似，我们思考后发现每个节点只有选和不选两种状态，有了这个想法

写起来就很轻松了，其实思考维护什么状态就是要看看我们设置啥样的状态才能计算出要求的值并且还要保证在求的过程中维护好题目要求的规则

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int e[N],ne[N],h[N],idx;
int n;
int ha[N];
int f1[N][2];
int f[N];void add(int a,int b){e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}void dfs(int u,int father){f1[u][0] = 0,f1[u][1] = ha[u];for(int i=h[u];~i;i=ne[i]){int j = e[i];if(j==father)continue;dfs(j,u);f1[u][0] = f1[u][0] + max(f1[j][1],f1[j][0]);f1[u][1] = f1[u][1] + f1[j][0];}}int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>ha[i];memset(h,-1,sizeof h);for(int i=1;i<n;i++){int a,b;cin>>a>>b;add(a,b),add(b,a);f[a] = b;}int root=1;while(f[root])root++;dfs(root,-1);cout<<max(f1[root][0],f1[root][1]);}