【BFS 动态规划】P12382 [蓝桥杯 2023 省 Python B] 树上选点|普及+

本文涉及知识点

C++动态规划
C++BFS算法

P12382 [蓝桥杯 2023 省 Python B] 树上选点

题目描述

给定一棵树，树根为 1 1 1，每个点的点权为 V i V_i Vi​。

你需要找出若干个点 P i P_i Pi​，使得：

1. 每两个点 P x , P y P_x,P_y Px​,Py​ 互不相邻；
2. 每两个点 P x , P y P_x,P_y Px​,Py​ 与树根的距离互不相同；
3. 找出的点的点权之和尽可能大。

请输出找到的这些点的点权和的最大值。

输入格式

输入的第一行包含一个整数 n n n。

第二行包含 n − 1 n-1 n−1 个整数 F i F_i Fi​，相邻整数之间使用一个空格分隔，分别表示第 2 至 n n n 个结点的父结点编号。

第三行包含 n n n 个整数 V i V_i Vi​，相邻整数之间使用一个空格分隔，分别表示每个结点的点权。

输出格式

输出一行包含一个整数表示答案。

输入输出样例 #1

输入 #1

5 1 2 3 2 2 1 9 3 5 

输出 #1

11 

说明/提示

评测用例规模与约定

• 对于 40 % 40\% 40% 的评测用例， n ≤ 5000 n \leq 5000 n≤5000；
• 对于所有评测用例， 1 ≤ n ≤ 2 × 10 5 1 \leq n \leq 2 \times 10^5 1≤n≤2×105， 1 ≤ F i < i 1 \leq F_i < i 1≤Fi​<i， 1 ≤ V i ≤ 10 4 1 \leq V_i \leq 10^4 1≤Vi​≤104。

P12382 [蓝桥杯 2023 省 Python B] 树上选点

性质一：任意父子节点，不会被同时选择。
性质二：任意层次都只有一个节点。
特殊情况：3个节点的链，根是2，权重分别为2,1,2。选择0层2层的2，不选第1层。
pre和cur记录上一层和当前层的信息。 c u r i = w w i , n o d e i cur_i={ww_i,node_i} curi​=wwi​,nodei​,表示node被选择，node的所有祖先所在层都已经选择的最大权值和是 w w i ww_i wwi​。pre类型，不赘述。
BFS出各层次的节点。初始pre = {{根节点权重,0},{0,-1}}，我习惯编号从0开始。
pre降序， curnode in 第i层的节点，如果curnode的父节点不是pre[0].node，j=0,否则j=1。 cur.emplace{pre[j].ww+当前节点权重，curnode}
cur.emplace({pre[0].ww,-1})表示不选择。
本题和普通滚动向量优化空间不同，cur swap之前，降序排序，只保留cur[0…1]，其它删除。
瓶颈在排序，时间复杂度：O(nlogn)。

代码

核心代码

#include<iostream>#include<sstream>#include<vector>#include<map>#include<unordered_map>#include<set>#include<unordered_set>#include<string>#include<algorithm>#include<functional>#include<queue>#include<stack>#include<iomanip>#include<numeric>#include<math.h>#include<climits>#include<assert.h>#include<cstring>#include<list>#include<array>#include<bitset>usingnamespace std;template<classT1,classT2> std::istream&operator>>(std::istream& in, pair<T1, T2>& pr){ in >> pr.first >> pr.second;return in;}template<classT1,classT2,classT3> std::istream&operator>>(std::istream& in, tuple<T1, T2, T3>& t){ in >>get<0>(t)>>get<1>(t)>>get<2>(t);return in;}template<classT1,classT2,classT3,classT4> std::istream&operator>>(std::istream& in, tuple<T1, T2, T3, T4>& t){ in >>get<0>(t)>>get<1>(t)>>get<2>(t)>>get<3>(t);return in;}template<classT1,classT2,classT3,classT4,classT5,classT6,classT7> std::istream&operator>>(std::istream& in, tuple<T1, T2, T3, T4,T5,T6,T7>& t){ in >>get<0>(t)>>get<1>(t)>>get<2>(t)>>get<3>(t)>>get<4>(t)>>get<5>(t)>>get<6>(t);return in;}template<classT=int> vector<T>Read(){int n; cin >> n; vector<T>ret(n);for(int i =0; i < n; i++){ cin >> ret[i];}return ret;}template<classT=int> vector<T>ReadNotNum(){ vector<T> ret; T tmp;while(cin >> tmp){ ret.emplace_back(tmp);if('\n'== cin.get()){break;}}return ret;}template<classT=int> vector<T>Read(int n){ vector<T>ret(n);for(int i =0; i < n; i++){ cin >> ret[i];}return ret;}template<int N =1'000'000>classCOutBuff{public:COutBuff(){ m_p = puffer;}template<classT>voidwrite(T x){int num[28], sp =0;if(x <0)*m_p++='-', x =-x;if(!x)*m_p++=48;while(x) num[++sp]= x %10, x /=10;while(sp)*m_p++= num[sp--]+48;AuotToFile();}voidwritestr(constchar* sz){strcpy(m_p, sz); m_p +=strlen(sz);AuotToFile();}inlinevoidwrite(char ch){*m_p++= ch;AuotToFile();}inlinevoidToFile(){fwrite(puffer,1, m_p - puffer,stdout); m_p = puffer;}~COutBuff(){ToFile();}private:inlinevoidAuotToFile(){if(m_p - puffer > N -100){ToFile();}}char puffer[N],* m_p;};template<int N =1'000'000>classCInBuff{public:inlineCInBuff(){}inline CInBuff<N>&operator>>(char& ch){FileToBuf();while(('\r'==*S)||('\n'==*S)||(' '==*S)){ S++;}//忽略空格和回车 ch =*S++;return*this;}inline CInBuff<N>&operator>>(int& val){FileToBuf();intx(0),f(0);while(!isdigit(*S)) f |=(*S++=='-');while(isdigit(*S)) x =(x <<1)+(x <<3)+(*S++^48); val = f ?-x : x; S++;//忽略空格换行 return*this;}inline CInBuff&operator>>(longlong& val){FileToBuf();longlongx(0);intf(0);while(!isdigit(*S)) f |=(*S++=='-');while(isdigit(*S)) x =(x <<1)+(x <<3)+(*S++^48); val = f ?-x : x; S++;//忽略空格换行return*this;}template<classT1,classT2>inline CInBuff&operator>>(pair<T1, T2>& val){*this>> val.first >> val.second;return*this;}template<classT1,classT2,classT3>inline CInBuff&operator>>(tuple<T1, T2, T3>& val){*this>>get<0>(val)>>get<1>(val)>>get<2>(val);return*this;}template<classT1,classT2,classT3,classT4>inline CInBuff&operator>>(tuple<T1, T2, T3, T4>& val){*this>>get<0>(val)>>get<1>(val)>>get<2>(val)>>get<3>(val);return*this;}template<classT=int>inline CInBuff&operator>>(vector<T>& val){int n;*this>> n; val.resize(n);for(int i =0; i < n; i++){*this>> val[i];}return*this;}template<classT=int> vector<T>Read(int n){ vector<T>ret(n);for(int i =0; i < n; i++){*this>> ret[i];}return ret;}template<classT=int> vector<T>Read(){ vector<T> ret;*this>> ret;return ret;}private:inlinevoidFileToBuf(){constint canRead = m_iWritePos -(S - buffer);if(canRead >=100){return;}if(m_bFinish){return;}for(int i =0; i < canRead; i++){ buffer[i]= S[i];//memcpy出错 } m_iWritePos = canRead; buffer[m_iWritePos]=0; S = buffer;int readCnt =fread(buffer + m_iWritePos,1, N - m_iWritePos,stdin);if(readCnt <=0){ m_bFinish =true;return;} m_iWritePos += readCnt; buffer[m_iWritePos]=0; S = buffer;}int m_iWritePos =0;bool m_bFinish =false;char buffer[N +10],* S = buffer;};classCBFSLeve{public:static vector<int>Leve(const vector<vector<int>>& neiBo, vector<int> start){ vector<int>leves(neiBo.size(),-1);for(constauto& s : start){ leves[s]=0;}for(int i =0; i < start.size(); i++){for(constauto& next : neiBo[start[i]]){if(-1!= leves[next]){continue;} leves[next]= leves[start[i]]+1; start.emplace_back(next);}}return leves;}template<classNextFun>static vector<int>Leve(int N, NextFun nextFun, vector<int> start){ vector<int>leves(N,-1);for(constauto& s : start){ leves[s]=0;}for(int i =0; i < start.size(); i++){auto nexts =nextFun(start[i]);for(constauto& next : nexts){if(-1!= leves[next]){continue;} leves[next]= leves[start[i]]+1; start.emplace_back(next);}}return leves;}static vector<vector<int>>LeveNodes(const vector<int>& leves){constint iMaxLeve =*max_element(leves.begin(), leves.end()); vector<vector<int>>ret(iMaxLeve +1);for(int i =0; i < leves.size(); i++){ ret[leves[i]].emplace_back(i);}return ret;};static vector<int>LeveSort(const vector<int>& leves){constint iMaxLeve =*max_element(leves.begin(), leves.end()); vector<vector<int>>leveNodes(iMaxLeve +1);for(int i =0; i < leves.size(); i++){ leveNodes[leves[i]].emplace_back(i);} vector<int> ret;for(constauto& v : leveNodes){ ret.insert(ret.end(), v.begin(), v.end());}return ret;};};classSolution{public:intAns(vector<int> par,const vector<int>& ws){constint N = ws.size(); par.insert(par.begin(),0); vector<vector<int>>neiBo(N);for(int i =0; i < N; i++){ par[i]--;if(0== i){continue;} neiBo[par[i]].emplace_back(i);}auto leves =CBFSLeve::Leve(neiBo,{0});auto leveNodes =CBFSLeve::LeveNodes(leves); vector<pair<int,int>> pre ={{ws[0],0},{0,-1}};for(int i =1; i < leveNodes.size(); i++){ vector<pair<int,int>> cur ={{pre[0].first,-1}};for(constauto& curNode : leveNodes[i]){constint j =(par[curNode]== pre[0].second)?1:0; cur.emplace_back(pre[j].first + ws[curNode], curNode);}sort(cur.begin(), cur.end(),greater<>()); cur.erase(cur.begin()+2, cur.end()); pre.swap(cur);}return pre[0].first;}};intmain(){#ifdef_DEBUGfreopen("a.in","r",stdin);#endif// DEBUG  ios::sync_with_stdio(0); cin.tie(nullptr);//CInBuff<> in; COutBuff<10'000'000> ob; int N; cin >> N;auto par =Read<int>(N -1);auto ws =Read<int>(N);#ifdef_DEBUG //printf("N=%d",N);Out(par,",par=");Out(ws,",ws=");//Out(P, ",P=");/*Out(edge, ",edge="); Out(que, ",que=");*///Out(ab, ",ab=");//Out(par, "par=");//Out(que, "que=");//Out(B, "B=");#endif// DEBUG auto res =Solution().Ans(par,ws); cout << res;return0;};

单元测试

vector<int> par , ws ;TEST_METHOD(TestMethod1){ par ={1,2,3,2}, ws ={2,1,9,3,5};auto res =Solution().Ans(par,ws);AssertEx(11, res);}

# 扩展阅读

视频课程

先学简单的课程，请移步ZEEKLOG学院，听白银讲师（也就是鄙人）的讲解。
https://edu.ZEEKLOG.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.ZEEKLOG.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。