蓝桥---蓝桥舞会---树状dp

思路

一直没想到树状dp的递推公式是什么！！也没有想到dp[i][0]表示以i为根的最大快乐指数（i不去舞会），dp[i][1]表示以i为根的最大快乐指数（i去舞会）。感觉这道题是dp+dfs的结合，而上一道题(病毒溯源）是dfs中就直接记录了dp，所以没有体现出dp。树状dp感觉都是后根遍历，就比如这道题，会凭借这几行代码找到叶节点。而病毒溯源（一维dp）是没有记录在dp中，直接用dfs()来代替dp[]的内容。

for(int k=h[i];k!=-1;k=nxt[k]){
    int p=e[k];
    dfs(p);
}

参考AcWing---病毒溯源---树状dp-CSDN博客思路及写法，我们来做一下这道题。

C++代码

#include <iostream>
using namespace std;

int h[100010];
int e[100010];
int nxt[100010];
int idx;
int n;
int a[100010];
int root[100010];
int dp[100010][2];//tql，第二个维度是选择or不选择，从来没这么考虑过
int head;


void add(int a,int b){
  e[idx]=b;
  nxt[idx]=h[a];
  h[a]=idx++;
}

int dfs(int i){//以i为根节点的最大快乐指数
  for(int k=h[i];k!=-1;k=nxt[k]){
    int p=e[k];
    dfs(p);
  }
  if(h[i]==-1){
    dp[i][0]=0;
    dp[i][1]=a[i];
    return a[i];
  }
  //dp[i][0]
  for(int k=h[i];k!=-1;k=nxt[k]){
    int p=e[k];
    dp[i][0]+=max(dp[p][1],dp[p][0]);
  }
  //dp[i][1]
  dp[i][1]=a[i];
  for(int k=h[i];k!=-1;k=nxt[k]){
    int p=e[k];
    dp[i][1]+=dp[p][0];
  }
  return max(dp[i][0],dp[i][1]);
}

int main()
{ 
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>a[i];
  }
  /*初始化h*/
  for(int i=1;i<=n;i++){h[i]=-1;}
  /*建树*/
  for(int i=1;i<=n-1;i++){
    int u,v;
    cin>>u>>v;
    root[u]=1;
    add(v,u);
  }
  /*找根*/
  for(int i=1;i<=n;i++){
    if(root[i]==0){
      head=i;
      break;
    }
  }

  /*dfs*/
  cout<<dfs(head);
  
  return 0;
}