没有上司的舞会题目地址题目要求最大的快乐指数用dp状态转移每个节点有两个状态来或者不来如果父节点来了那么子节点不来。1.首先我们先用邻接表存图intn;cinn;for(inti1;in;i)cina[i];// 每个来的快乐指数for(inti1;in;i){// n个点有n-1条边intu,v;cinuv;edges[u].push_back(v);// 存双向边edges[v].push_back(u);// 例如节点[1]所连接的边是234edges[1]{2,3,4}把当前节点对应的边都记录下来遍历边的时候不能跨边或者是不相连的边拿来操作2.这道题要用到二维dp,dp[当前节点][取不取]voiddfs(intu,intfa){dp[u][0]0;//进行初始化当前节点不取的话值是0dp[u][1]a[u];//取当前节点权值本身for(autoit:edges[u]){//遍历当前节点的所有边if(itfa)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];//选了的话子节点就不选了}}#includebits/stdc.husingnamespacestd;constintN6e35;inta[N];intdp[N][2];vectorintedges[N];voiddfs(intu,intfa){dp[u][0]0;dp[u][1]a[u];for(autoit:edges[u]){if(itfa)continue;dfs(it,u);dp[u][0]max(dp[it][0],dp[it][1]);dp[u][1]dp[it][0];}}intmain(){intn;cinn;for(inti1;in;i)cina[i];for(inti1;in;i){intu,v;cinuv;edges[u].push_back(v);edges[v].push_back(u);}dfs(1,1);coutmax(dp[1][0],dp[1][1])endl;// 要从根节点遍历下来先看最大的上司来不来在一层层遍历下来得到整棵树的值return0;}