专业网站建设方案,8718企业服务平台,西安网站建设定制,qq是用什么开发的有了上一篇博客#xff0c;没有看上一篇博客的可以看看上一篇博客#xff0c;我们对没有上司的舞会这道题会有更好的理解~ 所以关键的思路就是确定对于每一个节点我们应该维护什么内容才是最合适的#xff0c;这个题目和上一篇博客的最后一道题目很相似#xff0c;我们思考…有了上一篇博客没有看上一篇博客的可以看看上一篇博客我们对没有上司的舞会这道题会有更好的理解~ 所以关键的思路就是确定对于每一个节点我们应该维护什么内容才是最合适的这个题目和上一篇博客的最后一道题目很相似我们思考后发现每个节点只有选和不选两种状态有了这个想法
写起来就很轻松了其实思考维护什么状态就是要看看我们设置啥样的状态才能计算出要求的值并且还要保证在求的过程中维护好题目要求的规则
#includebits/stdc.h
using namespace std;
const int N 2e510;
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 ih[u];~i;ine[i]){int j e[i];if(jfather)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()
{cinn;for(int i1;in;i)cinha[i];memset(h,-1,sizeof h);for(int i1;in;i){int a,b;cinab;add(a,b),add(b,a);f[a] b;}int root1;while(f[root])root;dfs(root,-1);coutmax(f1[root][0],f1[root][1]);}
