柚子快報(bào)邀請碼778899分享：藍(lán)橋杯14屆真題-樹上選點(diǎn)

http://yzkb.51969.com/

按照樹的深度進(jìn)行dp 通過遞歸得到每個點(diǎn)的深度 通過一個 map數(shù)組 記錄 深度i上的 每個點(diǎn)為根的子樹的權(quán)值最大和，根據(jù)遍歷的點(diǎn)，刪除它的孩子節(jié)點(diǎn)作為根的子樹的權(quán)值最大和（這是選擇當(dāng)前節(jié)點(diǎn)的情況dp[u][1]）

#include

#include

#include

#include

using namespace std;

const int N = 200010;

// 點(diǎn)個數(shù)

int n;

// 鄰接表

int h[N],e[N], ne[N], idx;

//父數(shù)組

int f[N];

//深度數(shù)組

int dep[N];

// level[i]: 深度為i 的節(jié)點(diǎn)有哪些

vector level[N];

//樹的最大深度

int maxDepth;

//權(quán)值

int w[N];

// dp狀態(tài)數(shù)組

int dp[N][2]; // dp[i][0] 表示以i為根節(jié)點(diǎn)的子樹，在不選擇當(dāng)前節(jié)點(diǎn)的情況下的點(diǎn)權(quán)和最大值（以下統(tǒng)稱為 答案）

map max_dp_at_depth[N]; // max_dp_at_depth[i]: 數(shù)組元素是一個map; 鍵：深度為i的節(jié)點(diǎn)的答案 ; 值：出現(xiàn)了幾次

void add(int a, int b){ // a指向b的一條邊

e[idx] = b;

ne[idx] = h[a];

h[a] = idx++;

}

//遞歸實(shí)現(xiàn) 求每個點(diǎn)的深度

void dfs(int u, int p){

//子節(jié)點(diǎn)的深度是父節(jié)點(diǎn)的深度+1

dep[u] = dep[p]+1;

//更新最大深度

maxDepth = max(maxDepth, dep[u]);

// 當(dāng)前節(jié)點(diǎn)u，放到深度集合中

level[dep[u]].push_back(u);

//遍歷當(dāng)前節(jié)點(diǎn)的每個孩子

for(int i = h[u]; i!=-1; i = ne[i]){

int j = e[i];

dfs(j, u); //繼續(xù)往下遞歸

}

}

int main()

{

memset(h, -1, sizeof h);

scanf("%d", &n);

for(int i = 2; i <= n; i++){

int a;

scanf("%d", &a);

add(a,i);

f[i] = a;

}

for(int i = 1; i <= n; i++){

scanf("%d", &w[i]);

}

//更新每個點(diǎn)的深度

dfs(1,0);

// 按照深度進(jìn)行遍歷，從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)

for(int d = maxDepth; d; d--){

//從level中拿到當(dāng)前深度的所有節(jié)點(diǎn)，進(jìn)行遍歷

for(int i = 0; i < level[d].size(); i++){

int u = level[d][i]; //當(dāng)前節(jié)點(diǎn)

// 1. 不選擇當(dāng)前節(jié)點(diǎn)，那dp[u][0]可以來自 下一層深度上的答案的最大值（map默認(rèn)根據(jù)鍵從小到大排序，所以rbegin取最后一個答案）

if(max_dp_at_depth[d+1].size()){

dp[u][0] = max_dp_at_depth[d+1].rbegin()->first;

}

// 2. 當(dāng)選擇當(dāng)前時 , 每個子節(jié)點(diǎn)不能再選，所以再深度為d+1的答案map中刪除掉該答案（-1）

// 遍歷當(dāng)前節(jié)點(diǎn)u的每個子節(jié)點(diǎn)

for(int j = h[u]; j!=-1; j = ne[j]){

int child = e[j];

//把下一層深度上的 答案為dp[child][1]的情況的數(shù)量 減1

max_dp_at_depth[d+1][dp[child][1]] -= 1;

// 把下一層深度上的 答案為dp[child][1]的情況的數(shù)量變成0后，就在map中（max_dp_at_depth[d+1]）刪除該項(xiàng)

if(max_dp_at_depth[d+1][dp[child][1]] == 0){

max_dp_at_depth[d+1].erase(dp[child][1]);

}

}

// 但d+1層還有答案，也就是說是在同一層的不同子樹上， 選擇當(dāng)前節(jié)點(diǎn)的答案就是本身的權(quán)值+下一層的最大答案

if(max_dp_at_depth[d+1].size()){

dp[u][1] = w[u] + max_dp_at_depth[d+1].rbegin()->first;

}else{

dp[u][1] = w[u];

}

// 計(jì)算完成后， 恢復(fù)前面-=1減1操作

for(int j = h[u]; j != -1; j=ne[j]){

int child = e[j];

max_dp_at_depth[d+1][dp[child][1]] += 1;

}

// 把當(dāng)前深度上的答案保存下來

max_dp_at_depth[d][dp[u][0]] += 1;

max_dp_at_depth[d][dp[u][1]] += 1;

}

//為節(jié)省空間，把下兩層的答案清理到(此時d深度的已經(jīng)更新完了，d+1就不用了)

max_dp_at_depth[d+1].clear();

}

printf("%d", max(dp[1][0], dp[1][1]));

return 0;

}

支持點(diǎn)贊收藏喲?

柚子快報(bào)邀請碼778899分享：藍(lán)橋杯14屆真題-樹上選點(diǎn)

http://yzkb.51969.com/

推薦鏈接