P12027 [USACO25OPEN] Ski Slope S

题目描述

贝茜要和朋友们一起去滑雪。雪山上有NNN个路标（1≤N≤1051 \leq N \leq 10^51≤N≤105），按海拔从低到高依次标记为1,2,…,N1, 2, \ldots, N1,2,…,N（路标111位于山脚）。

对于每个路标i>1i > 1i>1，有一条从路标iii出发，终点为路标pip_ipi​（1≤pi<i1 \leq p_i < i1≤pi​<i）的滑雪道。这条滑道的难度为did_idi​（0≤di≤1090 \leq d_i \leq 10^90≤di​≤109），乐趣值为eie_iei​（0≤ei≤1090 \leq e_i \leq 10^90≤ei​≤109）。

贝茜的MMM个朋友（1≤M≤1051 \leq M \leq 10^51≤M≤105）每人会进行如下操作：选择一个起始路标iii，然后沿着滑道向下滑行（依次经过pi,ppip_i,p_{p_i}pi​,ppi​​，依此类推），直到抵达路标111。

每位朋友获得的乐趣值等于他们经过的所有滑道的乐趣值之和。每个朋友有不同的技能水平sjs_jsj​（0≤sj≤1090 \leq s_j \leq 10^90≤sj​≤109）和勇气值cjc_jcj​（0≤cj≤100 \leq c_j \leq 100≤cj​≤10），这限制他们选择的起始路标必须满足：滑行过程中最多有cjc_jcj​条滑道的难度超过sjs_jsj​。

请为每位朋友计算他们能获得的最大乐趣值。

输入格式

第一行包含NNN。

接下来222到NNN行，每行包含三个整数pip_ipi​，did_idi​和eie_iei​。

随后一行包含MMM。

接下来MMM行，每行包含两个整数sjs_jsj​和cjc_jcj​。

输出格式

输出MMM行，每行对应一个朋友的答案。

注意：由于涉及大整数运算，可能需要使用 64 位整数类型（如 C/C++ 中的long long）。

输入输出样例 #1

输入 #1

4 1 20 200 2 30 300 2 10 100 8 19 0 19 1 19 2 20 0 20 1 20 2 29 0 30 0

输出 #1

0 300 500 300 500 500 300 500

说明/提示

第一位朋友只能选择路标111作为起点，因为其他路标都会导致至少经过一条难度超过191919的滑道。总乐趣值为000。

第二位朋友可以选择路标444，依次滑行至路标222和111。总乐趣值为100+200=300100 + 200 = 300100+200=300，其中有一条滑道难度超过191919。

第三位朋友可以选择路标333，依次滑行至路标222和111。总乐趣值为300+200=500300 + 200 = 500300+200=500，其中有两条滑道难度超过191919。

• 测试点2∼42\sim42∼4：N,M≤1000N, M \leq 1000N,M≤1000。
• 测试点5∼75\sim75∼7：所有cj=0c_j = 0cj​=0。
• 测试点8∼178\sim178∼17：无额外限制。

C++实现

#include<bits/stdc++.h>usingnamespacestd;intn,p[100010],k;//一次性longlonge[100010],d[100010],_max[12][100010],ans[12][100010];structNode{longlonge,max_[12];booloperator<(constNode&x){returnmax_[k]<x.max_[k];}}a[100010];longlongmax_[12][100010];intmain(){cin>>n;for(inti=2;i<=n;i++){cin>>p[i]>>d[i]>>e[i];e[i]+=e[p[i]];a[i].e=e[i];for(intj=1;j<=11;j++)_max[j][i]=_max[j][p[i]];for(intj=1;j<=11;j++){if(d[i]>_max[j][i])swap(d[i],_max[j][i]);a[i].max_[j]=_max[j][i];}}for(k=1;k<=11;k++){sort(a+1,a+1+n);for(inti=2;i<=n;i++){ans[k][i]=max(ans[k][i-1],a[i].e);max_[k][i]=a[i].max_[k];}}intm;cin>>m;while(m--){ints,c;cin>>s>>c;c++;intid=upper_bound(max_[c]+1,max_[c]+n+1,s)-max_[c]-1;cout<<ans[c][id]<<'\n';}}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容