2023信奥赛C++提高组csp-s复赛真题及题解：种树

2023信奥赛C++提高组csp-s复赛真题及题解：种树

题目描述

你是一个森林养护员，有一天，你接到了一个任务：在一片森林内的地块上种树，并养护至树木长到指定的高度。

森林的地图有n nn片地块，其中1 11号地块连接森林的入口。共有n − 1 n-1n−1条道路连接这些地块，使得每片地块都能通过道路互相到达。最开始，每片地块上都没有树木。

你的目标是：在每片地块上均种植一棵树木，并使得i ii号地块上的树的高度生长到不低于a i a_iai​米。

你每天可以选择一个未种树且与某个已种树的地块直接邻接（即通过单条道路相连）的地块，种一棵高度为0 00米的树。如果所有地块均已种过树，则你当天不进行任何操作。特别地，第1 11天你只能在1 11号空地种树。

对每个地块而言，从该地块被种下树的当天开始，该地块上的树每天都会生长一定的高度。由于气候和土壤条件不同，在第x xx天，i ii号地块上的树会长高max ⁡ ( b i + x × c i , 1 ) \max(b_i + x \times c_i, 1)max(bi​+x×ci​,1)米。注意这里的x xx是从整个任务的第一天，而非种下这棵树的第一天开始计算。

你想知道：最少需要多少天能够完成你的任务？

输入格式

输入的第一行包含一个正整数n nn，表示森林的地块数量。

接下来n nn行：每行包含三个整数a i , b i , c i a_i, b_i, c_iai​,bi​,ci​，分别描述一片地块，含义如题目描述中所述。

接下来n − 1 n-1n−1行：每行包含两个正整数u i , v i u_i, v_iui​,vi​，表示一条连接地块u i u_iui​和v i v_ivi​的道路。

输出格式

输出一行仅包含一个正整数，表示完成任务所需的最少天数。

输入输出样例 1

输入 1

4 12 1 1 2 4 -1 10 3 0 7 10 -2 1 2 1 3 3 4

输出 1

5

说明/提示

【样例 1 解释】

第1 11天：在地块1 11种树，地块1 11的树木长高至2 22米。

第2 22天：在地块3 33种树，地块1 , 3 1, 31,3的树木分别长高至5 , 3 5, 35,3米。

第3 33天：在地块4 44种树，地块1 , 3 , 4 1, 3, 41,3,4的树木分别长高至9 , 6 , 4 9, 6, 49,6,4米。

第4 44天：在地块2 22种树，地块1 , 2 , 3 , 4 1, 2, 3, 41,2,3,4的树木分别长高至14 , 1 , 9 , 6 14, 1, 9, 614,1,9,6米。

第5 55天：地块1 , 2 , 3 , 4 1, 2, 3, 41,2,3,4的树木分别长高至20 , 2 , 12 , 7 20, 2, 12, 720,2,12,7米。

【样例 2】

见选手目录下的tree/tree2.in与tree/tree2.ans。

【样例 3】

见选手目录下的tree/tree3.in与tree/tree3.ans。

【样例 4】

见选手目录下的tree/tree4.in与tree/tree4.ans。

【数据范围】

对于所有测试数据有：1 ≤ n ≤ 10 5 , 1 ≤ a i ≤ 10 18 , 1 ≤ b i ≤ 10 9 , 0 ≤ ∣ c i ∣ ≤ 10 9 , 1 ≤ u i , v i ≤ n 1 \le n \le 10^5,1 \le a_i \le 10^{18}, 1 \le b_i \le 10^9,0 \le |c_i| \le 10^9, 1 \le u_i, v_i \le n1≤n≤105,1≤ai​≤1018,1≤bi​≤109,0≤∣ci​∣≤109,1≤ui​,vi​≤n。保证存在方案能在10 9 10^9109天内完成任务。

特殊性质A \text AA：对于所有1 ≤ i ≤ n 1 ≤ i ≤ n1≤i≤n，均有c i = 0 c_i = 0ci​=0；

特殊性质B \text BB：对于所有1 ≤ i < n 1 ≤ i < n1≤i<n，均有u i = i , v i = i + 1 u_i = i,v_i = i + 1ui​=i,vi​=i+1；

特殊性质C \text CC：与任何地块直接相连的道路均不超过2 22条；

特殊性质D \text DD：对于所有1 ≤ i < n 1 ≤ i < n1≤i<n，均有u i = 1 u_i = 1ui​=1。

思路分析

核心思路

这是一个树上的种植问题，需要在满足树形种植顺序和生长条件的前提下，最小化完成时间。

解题步骤

1. 二分答案：因为完成天数具有单调性（天数越多越容易完成），所以可以二分答案。
2. 检查函数(check)：对于给定的天数mx，检查是否能在mx天内完成所有种植。
3. 最晚种植时间计算：对每个节点，二分计算其最晚种植时间（满足生长条件）。
4. 树形约束处理：通过DFS更新最晚种植时间，确保父节点在子节点之前种植。
5. 可行性验证：使用计数排序检查是否存在可行的时间安排。

关键函数

1. calc函数：计算从第i天开始种植，到第n天结束的总生长量。

   • 考虑了生长速度递减的情况（c<0）
   • 当生长速度降为0时，后续每天只长1米
   • 对于c≥0的情况，使用等差数列求和公式

2. check函数：

   • 步骤1：计算每个节点的最晚种植时间（不考虑树形约束）
   • 步骤2：通过DFS考虑树形约束，更新最晚种植时间（父节点要比子节点早）
   • 步骤3：使用计数排序验证是否存在可行安排

算法复杂度

• 单次check：O(n log n)（每个节点二分+DFS遍历）
• 总复杂度：O(n log n log R)，其中R是答案上界

代码实现

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=100010;// 最大节点数intn;// 节点数量intfa[N];// 父节点（或最晚种植时间限制）intdp[N];// 临时数组intcnt[N];// 计数数组ll A[N],B[N],C[N];// 题目输入的a,b,c参数vector<int>g[N];// 图的邻接表// 计算从第i天开始种植，到第n天结束的总生长量inline__int128calc(ll i,ll n,__int128 a,__int128 b){if(a<0){// 生长速度递减的情况// 计算生长速度降为0的天数ll d=min((b-a-1)/(-a),(__int128)n+1);if(d<=i)returnn-i+1;// 全部时间都只长1米// 分两段计算：线性递减阶段+每天1米阶段returnn-d+1+(d-i)*b+(d-1+i)*(d-i)/2*a;}// 生长速度非负的情况，使用等差数列求和return(n+i)*(n-i+1)/2*a+b*(n-i+1);}// DFS遍历树，更新每个节点的最晚种植时间voiddfs(intx,intf){for(inty:g[x]){if(y!=f){dfs(y,x);fa[x]=min(fa[x],fa[y]-1);// 父节点要比子节点早种}}}// 检查给定天数mx是否可行boolcheck(intmx){// 计算每个节点的最晚种植时间for(inti=1;i<=n;i++){// 如果第1天开始种都达不到高度要求，直接返回falseif(A[i]>calc(1,mx,C[i],B[i]))returnfalse;// 二分查找最晚种植时间intl=1,r=n;while(l<r){intmid=(l+r+1)>>1;if(A[i]<=calc(mid,mx,C[i],B[i]))l=mid;elser=mid-1;}// 根节点必须在第1天种if(i==1)l=1;fa[i]=l;}// 通过DFS更新最晚种植时间，考虑树形约束dfs(1,0);// 检查是否有节点的最晚种植时间小于1for(inti=1;i<=n;i++){if(fa[i]<1)returnfalse;}// 使用计数排序检查可行性for(inti=1;i<=n;i++)cnt[i]=0;for(inti=1;i<=n;i++)cnt[fa[i]]++;for(inti=1;i<=n;i++){cnt[i]+=cnt[i-1];if(cnt[i]>i)returnfalse;// 前i天最多只能种i棵树}returntrue;}intmain(){// 输入scanf("%d",&n);for(inti=1;i<=n;i++){scanf("%lld%lld%lld",&A[i],&B[i],&C[i]);}for(inti=1,x,y;i<n;i++){scanf("%d%d",&x,&y);g[x].push_back(y);g[y].push_back(x);}// 二分答案intl=n,r=1e9;while(l<r){intmid=(l+r)>>1;if(check(mid))r=mid;elsel=mid+1;}// 输出答案printf("%d\n",l);return0;}

功能分析

1. 生长量计算模块

• 正确处理了生长速度递减的情况
• 使用__int128防止溢出
• 分段计算总生长量

2. 约束处理模块

• 树形约束：通过DFS确保父节点先于子节点种植
• 时间约束：验证每天最多只能种一棵树

3. 可行性检查模块

• 计数排序检查是否存在可行安排
• 充分必要条件：前i天最多只能安排i棵树的种植

4. 二分答案框架

• 高效搜索最小完成天数
• 上界设置为1e9（题目保证在1e9天内能完成）

专栏推荐：信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html

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

#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;}