题解：P12027 [USACO25OPEN] Ski Slope S

· · 题解

本题是 USACO25OPEN 银组实现难度略大的题，由于这只属于银组知识范围，所以在此我当然不会用什么高级数据结构或算法，仅仅是一个朴素的的预处理即可。

根据题意，本题等效于给定一棵树和 M 个查询，求满足指定条件的到根结点路径的最大边权和。由于本题询问量比较大，我们有两个方向：一个是带 \log 查询，还有一个是预处理。注意到本题 c_i \le 10，这透露给我们信息：可以预处理这 11 种勇气值情况，再由二分技能水平找到符合条件的最大乐趣值。

接下来考虑具体代码实现。我们可以由终点倒推，维护到每个出发点的前 11 大的难度值和总乐趣值。接下来，对于每种勇气值，我们分别对这些该勇气值加 1 大的难度值及乐趣值构成的结构体进行排序。（该勇气值加 1 大的难度值为临界情况，依此排序）接下来我们再遍历排序后的结构体数组，维护 [1,i] 上的乐趣最大值。接下来，对于每个查询，我们先对勇气值对号入座，再二分在排序后结构体数组中的定位，输出预处理出来的乐趣最大值即可。

时间复杂度 O(c⋅N\log N+M\log N)（c= 11，表示 c_i 值域大小）。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,p[100010],k;//一次性
long long e[100010],d[100010],_max[12][100010],ans[12][100010];
struct Node{
 long long e,max_[12];
 bool operator<(const Node& x)
 {return max_[k]<x.max_[k];
 }
}a[100010];
long long max_[12][100010];
int main()
{cin>>n;
 for(int i=2;i<=n;i++)
 {cin>>p[i]>>d[i]>>e[i];
  e[i]+=e[p[i]];
  a[i].e=e[i];
  for(int j=1;j<=11;j++)
  _max[j][i]=_max[j][p[i]];
  for(int j=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(int i=2;i<=n;i++)
  {ans[k][i]=max(ans[k][i-1],a[i].e);
   max_[k][i]=a[i].max_[k];
  }
 }
 int m;cin>>m;
 while(m--)
 {int s,c;
  cin>>s>>c;
  c++;
  int id=upper_bound(max_[c]+1,max_[c]+n+1,s)-max_[c]-1;
  cout<<ans[c][id]<<'\n';
 }
}