蓝桥杯算法训练-结点选择（树状dp）

问题描述

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

输入格式

第一行包含一个整数 n 。

接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。

接下来一共 n-1 行，每行描述树上的一条边。

输出格式

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

样例输入

5

1 2 3 4 5

1 2

1 3

2 4

2 5

样例输出

12

样例说明

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

数据规模与约定

对于20%的数据， n <= 20。

对于50%的数据， n <= 1000。

对于100%的数据， n <= 100000。

权值均为不超过1000的正整数。

问题分析

看完题目以后，第一反应是树状dp，每一个结点只有两种状态，选择与不选择，如果选择该点，那么dp[i][1] 为它的值加上他的子树dp[j][0]的最大值，如果不选择该点，那么他的值为它的子树的不选择与他相连的子节点的最大值。

对于叶子节点 dp[k][0] = 0, dp[k][1] = k点权值

对于非叶子节点i, dp[i][0] = ∑max(dp[j][0], dp[j][1]) (j是i的儿子) 

           dp[i][1] = i点权值 + ∑dp[j][0] (j是i的儿子)

           最大权值即为max(dp[0][0], dp[0][1]) 。

由于样例n达到10万，因此我采用链表表示法。

解题代码

#include <iostream>
#include <algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define rep(i,s,e) for(int i = s;i<e;i++)
using namespace std;
typedef long long ll;
/**
对于叶子节点 dp[k][0] = 0, dp[k][1] = k点权值
对于非叶子节点i,
dp[i][0] = ∑max(dp[j][0], dp[j][1]) (j是i的儿子)
dp[i][1] = i点权值 + ∑dp[j][0] (j是i的儿子)
最大权值即为max(dp[0][0], dp[0][1])
*/
const int maxn = 200000;
struct Edge {
    int from,to;
    Edge(int u,int v):from(u),to(v){}
};
int dp[maxn][2];
vector<int>G[maxn];
vector<Edge> edges;
struct TreeDp{
    int n;
    int m;
    void init(){
        cin>>this->n;
        for(int i = 0 ;i<n;i++) G[i].clear();
        edges.clear();
        for(int i = 0 ;i<maxn;i++) dp[i][0] = 0,dp[i][1] = 0;
        for(int i = 0 ;i<n;i++){
            cin>>dp[i][1];
        }
        for(int i= 0 ;i<n-1;i++){
            int u,v;
            cin>>u>>v;
            u--;
            v--;
            addEdge(u,v);
        }
    }
    void addEdge(int u,int v){
        edges.push_back((Edge){u,v});
        m = edges.size();
        G[u].push_back(m-1);
        edges.push_back((Edge){v,u});
        m = edges.size();
        G[v].push_back(m-1);
    }
    void dfs(int x,int pre){
        for(int i = 0 ;i<G[x].size();i++){
            Edge &e = edges[G[x][i]];
            int u = e.from;
            int v = e.to;
            if(v==pre) continue;
            dfs(v,x);
            dp[x][1] += dp[v][0];
            dp[x][0] += max(dp[v][0],dp[v][1]);
        }
    }
    void getAnswer(){
        dfs(0,-1);
        cout<<max(dp[0][0],dp[0][1]);

    }
};
int main(){
    TreeDp t;
    t.init();
    t.getAnswer();
}