一：基本原理

f[u,0]表示不包含u作为根节点欢乐度的最大值，f[u,1]则表示包含u作为根节点的欢乐度。
时间复杂度的分析，状态 * 状态转移次数，本质On，状态有2n，状态的转移就是滚动数组的形式
image.png

  • 首先处理树用图的方式，这一点处理的很好，上面的状态转移方程，状态的表示，非常的巧妙 ```cpp

    include

    include

using namespace std;

const int N = 6010;

int f[N][2]; // 每一个点两个状态 int hp[N]; // 输入不同点的高兴度 int h[N], ne[N], e[N], idx; bool has_father[N]; // 因为要找到一个根节点进行遍历，辅助找根节点

void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; // h和ne数组存储的值都是idx,e存储的是哪个点 }

void dfs(int u) { f[u][1] = hp[u]; // 选择这个点要首先加上这个点的欢乐度 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; //i是idx，用e数组进行转换，转换成对应的点 dfs(j); f[u][0] += max(f[j][0], f[j][1]); f[u][1] += f[j][0]; } }

int main() { int n; ios::sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; i++) { cin >> hp[i]; }

  1. memset(h, - 1, sizeof h); // 经常出现内存溢出和时间超过
  2. for (int i = 1; i <= n - 1; i++)
  3. {
  4.     int a, b;
  5.     cin >> a >> b;
  6.     add(b, a);
  7.     has_father[a] = true;
  8. }
  10. int root = 1; // 找有没有父亲节点的方法也非常巧妙
  11. while (has_father[root]) root++;
  13. dfs(root);
  15. cout << max(f[root][0], f[root][1]) << endl;
  16. return 0;

} ```