自动搬运

查看原文

来自洛谷，原作者为

	nbhs23a28 坐标浙江宁波，一个迷惘不知如何努力的新初三蒟蒻||触发未定义内容，挂分两行泪；Always trie,always lose(WA&TLE)||年度目标：CSP-J 360，CSP-S 300||不拿7级勾不认证||向蓝绿题进军

搬运于2025-08-24 23:12:14，当前版本为作者最后更新于2025-04-06 19:34:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题是 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';
 }
}