算法训练节点选择

问题描述

有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？

输入格式

第一行包含一个整数 n 。
接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。
接下来一共 n-1 行，每行描述树上的一条边。

输出格式

输出一个整数，代表选出的点的权值和的最大值。

样例输入

5
1 2 3 4 5
1 2
1 3
2 4
2 5

样例输出

样例说明

选择3、4、5号点，权值和为 3+4+5 = 12 。

数据规模与约定

对于20%的数据， n <= 20。
对于50%的数据， n <= 1000。
对于100%的数据， n <= 100000。
权值均为不超过1000的正整数。

这是一题树形DP的题目, 首先给出状态转移方程:
dp[i][2], 1代表选择i, 0代表不选择i
i代表父节点, j代表子节点, 当选择i节点时, j节点必然不选择, 当不选择i节点时, 则比较选择j节点和不选择j节点的情况选择大的

dp[i][1] = dp[j][0]
dp[i][0] = max(dp[j][0], dp[j][1])

一开始题没看仔细, 以为输入在前的代表父节点, 输入在后的代表子节点, 所以就错了:

#include <bits/stdc++.h>
#define MAXN 100010
using namespace std;

int dp[MAXN][2], father[MAXN];
bool visited[MAXN];
int n, root;

void treeDp(int node) {
    visited[node] = true;
    for(int i = 1; i <= n; i++) {
        if(!visited[i] && father[i] == node) {
            treeDp(i);
            dp[node][1] += dp[i][0];
            dp[node][0] += max(dp[i][0], dp[i][1]);
        }
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &dp[i][1]);
    }
    int f, c;
    bool begin = true;
    root = 0;
    for(int i = 1; i < n; i++) {
        scanf("%d%d", &f, &c);
        father[c] = f;
        if(root == c || begin) {
            root = f;
            begin = true;
        }
    }
    while(father[root]) {
        root = father[root];
    }
     
    treeDp(root);
    int ans = max(dp[root][0], dp[root][1]);
    printf("%d\n", ans);
    
    return 0;
}

还是too young too simple啊, 这里只是告诉了两个节点形成了一条边, 并没有告诉谁是父节点, 谁是子节点, 所以这里需要使用前向星来存储树

#include <bits/stdc++.h>
#define MAXN 100010
using namespace std;

struct {
    int v;
    int next;
}edge[MAXN * 2];
int dp[MAXN][2], head[MAXN];
int M;

void add(int from, int to) {
    edge[M].v = to;
    edge[M].next = head[from];
    head[from] = M++;
    edge[M].v = from;
    edge[M].next = head[to];
    head[to] = M++;
}

void treeDp(int x, int pre) {
    for (int i = head[x]; i != -1; i = edge[i].next) {
        int v = edge[i].v;
        if(pre == v)
            continue;
        treeDp(v, x);
        dp[x][1] += dp[v][0];
        dp[x][0] += max(dp[v][0], dp[v][1]); 
    }
}

int main() {
    int n;
    M = 0;
    scanf("%d", &n);
    memset(dp, 0, sizeof(dp));
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= n; i++) {
        scanf("%d", &dp[i][1]);
    }
    int c, f;
    for(int i = 1; i < n; i++) {
        scanf("%d%d", &c, &f);
        add(c, f);
    }
    treeDp(1, -1);
    int ans = max(dp[1][0], dp[1][1]);
    printf("%d\n", ans);
    
    
    return 0;
}

算法训练 节点选择