题目：P1352 没有上司的舞会 算法标签：dp，搜索，树形结构，记忆化搜索
从树的头往下求结果会有后效性，且有多个叶子节点，数据不易处理 则采用，叶子节点往头部求结果
对于某一节点，有选择和不选择两种情况 1、不选择的话 记 dp[ ][ 0 ]
for(int i = 0; i < a[x].tail.size(); i++){ f[x][0] += max(f[son][0], f[son][1]); }2、选择的话 记dp[ ][ 1 ]
for(int i = 0; i < a[x].tail.size(); i++){ f[x][1] += f[son][0]; } #include <bits/stdc++.h> using namespace std; const int maxn = 6e3 + 5; struct node { int r; vector<int> tail; }a[maxn]; int n, head; int f[maxn][3]; bool vis[maxn]; void dp(int x){ f[x][0] = 0; f[x][1] = a[x].r; for(int i = 0; i < a[x].tail.size(); i++){ int son = a[x].tail[i]; dp(son); f[x][0] += max(f[son][0], f[son][1]); f[x][1] += f[son][0]; } } int main(){ cin >> n; int k, l, ans = 0; for(int i = 1; i <= n; i++){ cin >> a[i].r; } for(int i = 1; i < n; i++){ cin >> l >> k; a[k].tail.push_back(l); vis[l] = true; // 标记该节点并非根 } // 找出根 for(int i = 1; i <= n; i++){ if(!vis[i]){ head = i; break; } } dp(head); cout << max(f[head][0], f[head][1]) << endl; return 0; } ```