比赛 |
2025.9.6 |
评测结果 |
AAAAAAAAAAAAAAAAA |
题目名称 |
Ski Slope |
最终得分 |
100 |
用户昵称 |
左清源 |
运行时间 |
3.018 s |
代码语言 |
C++ |
内存使用 |
31.74 MiB |
提交时间 |
2025-09-06 10:46:59 |
显示代码纯文本
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,p[N],d[N],e[N],v[N];
int ver[N],to[N<<1],nxt[N<<1],val[N<<1],cost[N<<1],idx;
struct node{
int a[15];
void init(){
for(int i=1;i<=11;i++)a[i]=-0x3f3f3f3f;
}
void ins(int x){
if(x<a[11])return;
int pos;
for(int i=1;i<=11;i++){
if(x>a[i]){
pos=i;break;
}
}
for(int i=11;i>pos;i--)a[i]=a[i-1];
a[pos]=x;
return;
}
}lim[N];
void add(int x,int y,int z,int c){
to[++idx]=y,nxt[idx]=ver[x],ver[x]=idx,val[idx]=z,cost[idx]=c;
}
void dfs(int x){
for(int i=ver[x];i;i=nxt[i]){
int y=to[i];
v[y]=v[x]+val[i];
lim[y]=lim[x];
lim[y].ins(cost[i]);
dfs(y);
}
}
int rk,fd[14][N],ans[14][N];
bool cmp(int a,int b){
return lim[a].a[rk]<lim[b].a[rk];
}
signed main(){
freopen("Ski.in","r",stdin);
freopen("Ski.out","w",stdout);
scanf("%lld",&n);
for(int i=2;i<=n;i++){
scanf("%lld %lld %lld",p+i,d+i,e+i);
add(p[i],i,e[i],d[i]);
}
for(int i=1;i<=n;i++)lim[i].init();
dfs(1);
for(int j=1;j<=11;j++){
for(int i=1;i<=n;i++)ans[j][i]=i;
}
for(int i=1;i<=11;i++){
rk=i;
sort(ans[i]+1,ans[i]+1+n,cmp);
}
for(int j=1;j<=11;j++){
//cout<<v<<endl;
for(int i=1;i<=n;i++){
//cout<<ans[v][i]<<"-"<<lim[ans[v][i]].a[v]<<" ";
fd[j][i]=lim[ans[j][i]].a[j];
ans[j][i]=v[ans[j][i]];
ans[j][i]=max(ans[j][i],ans[j][i-1]);
//cout<<ans[j][i]<<" ";
}
//cout<<endl;
}
int q,s,c,p;
scanf("%lld",&q);
while(q--){
scanf("%lld %lld",&s,&c);
c++;
p=upper_bound(fd[c]+1,fd[c]+1+n,s)-fd[c]-1;
//cout<<p<<endl;
printf("%lld\n",ans[c][p]);
}
return 0;
}