#include int ri() { int n; scanf("%d", &n); return n; } struct Query { int range; int weight; int id; }; struct AVL { struct Node { Node *l; Node *r; int size; int height; int key; int val; int64_t sum; Node *fetch() { size = 1 + l->size + r->size; height = 1 + std::max(l->height, r->height); sum = val + l->sum + r->sum; return this; } Node *rotate_l() { Node *new_root = r; r = new_root->l; new_root->l = this; return fetch(), new_root->fetch(); } Node *rotate_r() { Node *new_root = l; l = new_root->r; new_root->r = this; return fetch(), new_root->fetch(); } int height_diff() { return l->height - r->height; } Node *balance() { int dif = height_diff(); if (dif == 2) { if (l->height_diff() < 0) l = l->rotate_l(); return rotate_r(); } else if (dif == -2) { if (r->height_diff() > 0) r = r->rotate_r(); return rotate_l(); } else return fetch(); } }; static Node *nodes, *NONE; Node *root = NONE; static int head; AVL () { if (!head) nodes[head++] = {NONE, NONE, 0, 0, 0, 0, 0}; } static Node *insert(Node *node, int key, int val) { if (node == NONE) return &(nodes[head++] = {NONE, NONE, 1, 1, key, val, val}); if (key < node->key) node->l = insert(node->l, key, val); else if (key > node->key) node->r = insert(node->r, key, val); else assert(0); return node->balance(); } static int64_t sum(Node *node, int r) { if (node == NONE) return 0; if (node->key < r) return node->l->sum + node->val + sum(node->r, r); else return sum(node->l, r); } void insert(int key, int val) { root = insert(root, key, val); } int64_t sum(int r) { return sum(root, r); } static void reset() { if (head) head = 1; } void clear() { root = NONE; } }; AVL::Node *AVL::nodes = new Node[5000000], *AVL::NONE = nodes; int AVL::head = 0; std::vector > hen; std::vector size; std::vector alive; std::vector > qs; void dfs1(int i, int prev) { size[i] = qs[i].size() + 1; for (auto j : hen[i]) if (j != prev && alive[j]) { dfs1(j, i); size[i] += size[j]; } } int centroid(int i) { dfs1(i, -1); int minimum = (size[i] + 1) / 2; while (1) { int next = -1; for (auto j : hen[i]) if (alive[j] && size[j] < size[i] && size[j] >= minimum) next = j; if (next == -1) break; i = next; } return i; } std::vector adds, getqs; std::vector depth; void dfs2(int i, int prev) { for (auto j : qs[i]) { if (j.range >= depth[i]) adds.push_back({j.range - depth[i], j.weight, j.id}); getqs.push_back({depth[i], 0, j.id}); } for (auto j : hen[i]) if (j != prev && alive[j]) { depth[j] = depth[i] + 1; dfs2(j, i); } } std::vector res; void centroid_rec(int i) { // std::cerr << i << " " << centroid(i) << std::endl; i = centroid(i); std::vector > add_all, get_all; int group = 0; for (auto j : hen[i]) if (alive[j]) { adds.clear(); getqs.clear(); depth[j] = 1; dfs2(j, i); for (auto i : adds) add_all.push_back({group, i}); for (auto i : getqs) get_all.push_back({group, i}); group++; } for (auto j : qs[i]) { add_all.push_back({group, {j.range, j.weight, j.id}}); get_all.push_back({group, {0, 0, j.id}}); } std::sort(add_all.begin(), add_all.end(), [] (auto &i, auto &j) { return i.second.range > j.second.range; }); std::sort(get_all.begin(), get_all.end(), [] (auto &i, auto &j) { return i.second.range > j.second.range; }); /* for (auto i : get_all) std::cerr << " GET " << i.second.range << " " << i.second.weight << " " << i.second.id << std::endl; for (auto i : add_all) std::cerr << " ADD " << i.second.range << " " << i.second.weight << " " << i.second.id << std::endl; */ int head = 0; AVL all; AVL each[group + 1]; for (auto j : get_all) { while (head < (int) add_all.size() && add_all[head].second.range >= j.second.range) { all.insert(add_all[head].second.id, add_all[head].second.weight); each[add_all[head].first].insert(add_all[head].second.id, add_all[head].second.weight); head++; } res[j.second.id] += all.sum(j.second.id); if (j.first != group) res[j.second.id] -= each[j.first].sum(j.second.id); } alive[i] = false; for (auto j : hen[i]) if (alive[j]) centroid_rec(j); } int main() { int n = ri(); int q = ri(); hen.resize(n); for (int i = 1; i < n; i++) { int a = ri() - 1; int b = ri() - 1; hen[a].push_back(b); hen[b].push_back(a); } qs.resize(n); for (int i = 0; i < q; i++) { int a = ri() - 1; int b = ri(); int c = ri(); qs[a].push_back({b, c, i}); } size.resize(n); alive.resize(n, true); depth.resize(n); res.resize(q); centroid_rec(0); for (auto i : res) printf("%" PRId64 "\n", i); return 0; }