2024年12月GESP真题及题解(C++七级): 燃烧

2024年12月GESP真题及题解(C++七级): 燃烧

题目描述

小杨有一棵包含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​的边。

输出格式

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

输入输出样例 1

输入 1

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

输出 1

3

说明/提示

对于全部数据，保证有1 ≤ n ≤ 10 5 1\leq n\leq 10^51≤n≤105，1 ≤ a i ≤ 10 6 1\leq a_i\leq 10^61≤ai​≤106。

思路分析

燃烧规则可以理解为：从初始节点出发，沿着权值严格递减的路径可以到达的所有节点都会被点燃。由于树中任意两点间路径唯一，因此从节点 (u) 出发能点燃的节点集合，就是所有满足从 (u) 到该节点的路径上权值严格递减的节点。

我们定义 f[u]表示从节点 u出发能点燃的节点个数（包含 u自身）。考虑树的结构，从 (u) 出发经过不同邻居所能到达的节点集合互不相交（否则会违反树中路径的唯一性）。因此，对于 (u) 的每个邻居 (v)，如果a u > a v a_u > a_vau​>av​，那么从 (u) 可以到达 (v) 以及从 (v) 出发能到达的所有节点，且这些节点不会与其他邻居的可达节点重复。于是有状态转移：

$
f[u] = 1 + \sum_{v \in \text{邻居}(u), \ a_u > a_v} f[v]
$

计算顺序：由于燃烧只能向权值更小的节点传播，所以应先计算权值小的节点的 (f) 值。因此将所有节点按权值升序排序，依次计算即可。注意权值相等的节点之间没有传播关系，它们的计算顺序任意。

算法复杂度：排序 O(n log n)，遍历所有边 O(n)，总复杂度 O(n log n)，可以通过。

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+5;intn,a[N],f[N];vector<int>g[N];// 邻接表存树intmain(){ios::sync_with_stdio(false);cin.tie(0);// 读入数据cin>>n;for(inti=1;i<=n;++i)cin>>a[i];for(inti=1;i<n;++i){intu,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}// 初始化：每个节点至少可以点燃自己for(inti=1;i<=n;++i)f[i]=1;// 将节点按权值升序排序，便于DPvector<int>idx(n);iota(idx.begin(),idx.end(),1);// 生成1,2,...,nsort(idx.begin(),idx.end(),[&](intx,inty){returna[x]<a[y];});// 按权值从小到大计算每个节点的f值for(intu:idx){for(intv:g[u]){if(a[u]>a[v]){f[u]+=f[v];// 累加可达节点数}}}// 找出最大的f值即为答案intans=*max_element(f+1,f+n+1);cout<<ans<<endl;return0;}

功能分析

1. 数据读入与存储：使用邻接表存储树结构，数组a存储节点权值。
2. 状态定义与初始化：f[i]表示从节点i出发能点燃的节点数，初始化为1（包含自身）。
3. 排序与动态规划：将节点按权值升序排序，保证计算当前节点时，所有权值更小的邻居（即可能被点燃的节点）的f值已经计算完成。对于每个节点，遍历其邻居，若当前节点权值大于邻居权值，则将邻居的f值累加到当前节点。
4. 答案输出：遍历所有节点的f值，取最大值输出。

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

4、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}