题意

• 给定一颗n个结点的树，结点编号1~n，每个结点有权值，一个点选择以后，它的父亲就不可以被选，输出能选出的最大权值

思路

• 对于每个点，都有选和不选两种情况，当一个点选的时候，所有的儿子都不能选，当一个点不选的时候，每个儿子取选和不选的最大值即可，维护一个二维dp数组，状态转移方程如下
• 注意到，由于涉及父子关系，所以考虑用有根树来维护，因为输入的时候每个除了根以外的结点都只出现一次，根不出现，所以用编号和不断减去结点编号，最终剩余的就是根
• 当然，本题也可以使用无根树来维护

代码

#include<bits/stdc++.h>
//有根树
using namespace std;
int a[10101],dp[10101][2];
vector<int> s[10101];

void dfs(int x){
    dp[x][1]=a[x];
    dp[x][0]=0;
    for(auto i : s[x]){
        dfs(i);
        dp[x][0]+=max(dp[i][0],dp[i][1]);
        dp[x][1]+=dp[i][0];
    }
}

int main(){
    int n;
    cin >> n ;
    int root = n*(n+1)/2;
    for(int i=1;i<=n;i++){
        cin >> a[i] ;
    }
    for(int i=1;i<n;i++){
        int l,k;
        cin >> l >> k ;
        root -= l;
        s[k].push_back(l);
    }
    dfs(root);
    int ans = 0 ;
    for(int i=1;i<=n;i++){
        ans = max(dp[i][0],ans);
        ans = max(dp[i][1],ans);
    }
    cout << ans << endl;
    return 0;
}

//无根树
#include <bits/stdc++.h>


using namespace std;
const int maxn = 6000+10;
int f[maxn];
vector<int> v[maxn];
int dp[maxn][2];

void dfs(int x, int fa) {
    int len = v[x].size();
    dp[x][1] = f[x];
    for (int i=0;i<len;i++) {
        int next = v[x][i];
        if (next == fa) continue;
        dfs(next, x);
        dp[x][1] += dp[next][0];
        dp[x][0] += max(dp[next][0], dp[next][1]);
    }
}

int main() {
    int n;
    int x, y;
    cin>>n;
    for (int i=1;i<=n;i++) {
        cin>>f[i];
    }
    for (int i=1;i<=n;i++) {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1, 0);
    cout<<(dp[1][0]>dp[1][1]? dp[1][0]:dp[1][1]);
    return 0;
}