企业官网建设流程全解析

没有上司的舞会

题目地址

题目要求最大的快乐指数，用dp状态转移，每个节点有两个状态，来或者不来，如果父节点来了，那么子节点不来。
1.首先我们先用邻接表存图

intn;cin>>n;for(inti=1;i<=n;i++)cin>>a[i];// 每个来的快乐指数for(inti=1;i<n;i++){// n个点有n-1条边intu,v;cin>>u>>v;edges[u].push_back(v);// 存双向边edges[v].push_back(u);// 例如：节点[1]所连接的边是2，3，4；edges[1]={2,3,4}；把当前节点对应的边都记录下来（遍历边的时候不能跨边或者是不相连的边拿来操作）

2.这道题要用到二维dp,dp[当前节点][取不取]

voiddfs(intu,intfa){dp[u][0]=0;//进行初始化，当前节点不取的话值是0；dp[u][1]=a[u];//取=当前节点权值本身for(autoit:edges[u]){//遍历当前节点的所有边if(it==fa)continue;//防止死递归重复遍历，因为节点会来回遍历dfs(it,u);//这里进行递归是因为它需要算子节点的来和不来的值，通过这样一层层算出子节点的值，dp[it][0],dp[it][1]如果不递归我们是不知道的dp[u][0]+=max(dp[it][0],dp[it][1]);//如果当前节点不来，那么他的子节点可来可不来，选最大的，+=是因为他的值是需要累计的不是只算当前节点的值而是要我们所有加起来的值dp[u][1]+=dp[it][0];//选了的话，子节点就不选了}}

#include<bits/stdc++.h>usingnamespacestd;constintN=6e3+5;inta[N];intdp[N][2];vector<int>edges[N];voiddfs(intu,intfa){dp[u][0]=0;dp[u][1]=a[u];for(autoit:edges[u]){if(it==fa)continue;dfs(it,u);dp[u][0]+=max(dp[it][0],dp[it][1]);dp[u][1]+=dp[it][0];}}intmain(){intn;cin>>n;for(inti=1;i<=n;i++)cin>>a[i];for(inti=1;i<n;i++){intu,v;cin>>u>>v;edges[u].push_back(v);edges[v].push_back(u);}dfs(1,1);cout<<max(dp[1][0],dp[1][1])<<endl;// 要从根节点遍历下来，先看最大的上司来不来，在一层层遍历下来，得到整棵树的值return0;}