记录编号	605667	评测结果	AAAAAAAAAAAAAAAAA
题目名称	4172.[USACO25 Open Silver]Ski Slope	最终得分	100
用户昵称	OTTF	是否通过	通过
代码语言	C++	运行时间	5.127 s
提交时间	2025-09-06 12:32:16	内存使用	17.17 MiB

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
#include <set>

using namespace std;

constexpr int N = 114514;

template <typename T>
void read (T& num) {
    T res = 0;
	T ch = getchar();
	T op = 1;

    while (!isdigit (ch) && ch != EOF) {
		op = (ch == '-' ? -1 : 1);
        ch = getchar ();
	}

    while (isdigit (ch)) {
        res = (res * 10) + (ch - '0');
        ch = getchar ();
    }
    num = op * res;
}

class Read {
	public:
	Read operator>> (auto& other) {
		read (other);
		return (*this);
	}
};

Read in;

int n;
int m;
vector<int> tree[N];
struct node {
	long long num;
	int id;
	int type;

	node (long long num, int id, int type) : num (num), id (id), type (type) {

	}

	bool operator< (const node other) const{
		if (num != other.num) {
			return num > other.num;
		}
		return type > other.type;
	}
};
vector<node> vec;
long long sum[N];
int c[N];
set<pair<long long, int>> st[11];
int cc[N];
long long res[N];

void calSum (int now) {
	for (auto son : tree[now]) {
		sum[son] += sum[now];
		calSum (son);
	}
}

void ccPlus (int now) {
	if (cc[now] > 10) {
		return;
	}
	st[cc[now]].erase({-sum[now], now});
	cc[now]++;
	if (cc[now] <= 10) {
		st[cc[now]].insert({-sum[now], now});
	}

	for (auto son : tree[now]) {
		ccPlus (son);
	}
}

int main () {
	
	freopen ("Ski.in", "r", stdin);
	freopen ("Ski.out", "w", stdout);

	in >> n;
	int p, d;
	for (int i = 2; i <= n; i++) {
		in >> p >> d >> sum[i];
		tree[p].push_back(i);
		vec.emplace_back(d, i, 0);
	}
	calSum (1);

	in >> m;
	int s;
	for (int i = 1; i <= m; i++) {
		in >> s >> c[i];
		vec.emplace_back(s, i, 1);
	}

	for (int i = 1; i <= n; i++) {
		st[0].insert({-sum[i], i});
	}
	sort (vec.begin(), vec.end());
	for (auto [num, id, type] : vec) {
		if (type == 0) {
			ccPlus (id);
		}
		else {
			for (int i = 0; i <= c[id]; i++) {
				for (auto [numm, idd] : st[i]) {
					res[id] = max (res[id], -numm);
					break;
				}
			}
		}
	}

	for (int i = 1; i <= m; i++) {
		printf ("%lld\n", res[i]);
	}
	
	return 0;
}