记录编号	605725	评测结果	AAAAAAAAAAAAAAAAA
题目名称	4172.[USACO25 Open Silver]Ski Slope	最终得分	100
用户昵称	左清源	是否通过	通过
代码语言	C++	运行时间	3.140 s
提交时间	2025-09-06 17:22:11	内存使用	31.72 MiB

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