郑州市网站建设_网站建设公司_Linux_seo优化

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

【题目来源】

洛谷：P11378 [GESP202412 七级] 燃烧 - 洛谷

【题目描述】

小杨有一棵包含n nn个节点的树，其中节点的编号从1 11到n nn。节点i ii的权值为a i a_iai​。

小杨可以选择一个初始节点引燃，每个燃烧的节点会将其相邻节点中权值严格小于自身权值的节点也引燃，火焰会在节点间扩散直到不会有新的节点被引燃。

小杨想知道在合理选择初始节点的情况下，最多可以燃烧多少个节点。

【输入】

第一行包含一个正整数n nn，代表节点数量。

第二行包含n nn个正整数a 1 , a 2 , … , a n a_1,a_2,\dots,a_na1​,a2​,…,an​，代表节点权值。

之后n − 1 n-1n−1行，每行包含两个正整数u i , v i u_i,v_iui​,vi​，代表存在一条连接节点u i u_iui​和v i v_ivi​的边。

【输出】

输出一个正整数，代表最多燃烧的节点个数。

【输入样例】

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

【输出样例】

3

【算法标签】

《洛谷 P11378 燃烧》 #动态规划DP# #树形DP# #树的遍历# #GESP# #2024#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=100005;// 最大节点数constintM=N*2;// 无向图边数要×2intn;// 节点数量inta[N];// a[i]: 节点i的值intdp[N];// dp[i]: 以节点i为起点的最长递降路径长度intans;// 全局答案，最长路径长度inth[N],e[M],ne[M],idx;// 邻接表存储图// 添加一条a到b的无向边voidadd(inta,intb){e[idx]=b;// 存储终点ne[idx]=h[a];// 头插法h[a]=idx++;// 更新头节点}// 深度优先搜索，返回以u为起点的最长递降路径长度intdfs(intu){// 记忆化：如果已经计算过，直接返回结果if(dp[u]!=-1){returndp[u];}// 至少包含自己，所以初始长度为1intres=1;// 遍历u的所有邻居节点for(inti=h[u];i!=-1;i=ne[i]){intj=e[i];// 邻居节点j// 如果节点u的值大于邻居节点j的值，说明可以向下延伸if(a[u]>a[j]){// 递归计算以j为起点的路径长度// 加上u节点自身res+=dfs(j);}}// 记忆化存储结果dp[u]=res;returndp[u];}intmain(){cin>>n;// 输入节点数// 初始化邻接表memset(h,-1,sizeof(h));// 输入每个节点的值for(inti=1;i<=n;i++){cin>>a[i];}// 输入n-1条边，构建树for(inti=1;i<n;i++){intu,v;cin>>u>>v;add(u,v);// 添加u->v的边add(v,u);// 添加v->u的边，因为是无向图}// 初始化dp数组为-1，表示未计算memset(dp,-1,sizeof(dp));// 以每个节点为起点计算最长递降路径ans=0;// 初始化答案为0for(inti=1;i<=n;i++){ans=max(ans,dfs(i));}// 输出最长递降路径长度cout<<ans<<endl;return0;}

【运行结果】

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