#line 1 "main.cpp" #define PROBLEM "https://yukicoder.me/problems/no/1038" #line 2 "/home/maspy/library/my_template.hpp" #include using namespace std; using ll = long long; using ll8 = __int128; using ld = long double; using pi = pair; using vi = vector; using uint = unsigned int; using ull = unsigned long long; template using vc = vector; template using vvc = vector>; template using vvvc = vector>; template using vvvvc = vector>; template using vvvvvc = vector>; template using pq = priority_queue; template using pqg = priority_queue, greater>; #define vec(type, name, ...) vector name(__VA_ARGS__) #define VEC(type, name, size) \ vector name(size); \ IN(name) #define vv(type, name, h, ...) \ vector> name(h, vector(__VA_ARGS__)) #define VV(type, name, h, w) \ vector> name(h, vector(w)); \ IN(name) #define vvv(type, name, h, w, ...) \ vector>> name( \ h, vector>(w, vector(__VA_ARGS__))) #define vvvv(type, name, a, b, c, ...) \ vector>>> name( \ a, vector>>( \ b, vector>(c, vector(__VA_ARGS__)))) #define FOR(i, n) for (ll i = 0; (i) < (ll)(n); ++(i)) #define FOR3(i, m, n) for (ll i = (m); (i) < (ll)(n); ++(i)) #define FOR_R(i, n) for (ll i = (ll)(n)-1; (i) >= 0; --(i)) #define FOR3_R(i, m, n) for (ll i = (ll)(n)-1; (i) >= (ll)(m); --(i)) #define FOR_subset(t, s) for (ll t = s; t >= 0; t = (t == 0 ? -1 : (t - 1) & s)) #define all(x) x.begin(), x.end() #define len(x) ll(x.size()) #define elif else if #define eb emplace_back #define mp make_pair #define mt make_tuple #define fi first #define se second int popcnt(int x) { return __builtin_popcount(x); } int popcnt(uint x) { return __builtin_popcount(x); } int popcnt(ll x) { return __builtin_popcountll(x); } int popcnt(ull x) { return __builtin_popcountll(x); } // (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2) int topbit(int x) { return 31 - __builtin_clz(x); } int topbit(uint x) { return 31 - __builtin_clz(x); } int topbit(ll x) { return 63 - __builtin_clzll(x); } int topbit(ull x) { return 63 - __builtin_clzll(x); } // (0, 1, 2, 3, 4) -> (32 or 64, 0, 1, 0, 2) int lowbit(int x) { return 31 - __builtin_clz(x); } int lowbit(uint x) { return 31 - __builtin_clz(x); } int lowbit(ll x) { return 63 - __builtin_clzll(x); } int lowbit(ull x) { return 63 - __builtin_clzll(x); } ll ceil(ll x, ll y) { return (x > 0 ? (x + y - 1) / y : x / y); } ll floor(ll x, ll y) { return (x > 0 ? x / y : (x - y + 1) / y); } pi divmod(ll x, ll y) { ll q = floor(x, y); return {q, x - q * y}; } #define INT(...) \ int __VA_ARGS__; \ IN(__VA_ARGS__) #define LL(...) \ ll __VA_ARGS__; \ IN(__VA_ARGS__) #define STR(...) \ string __VA_ARGS__; \ IN(__VA_ARGS__) #define CHR(...) \ char __VA_ARGS__; \ IN(__VA_ARGS__) #define DBL(...) \ long double __VA_ARGS__; \ IN(__VA_ARGS__) void scan(int &a) { cin >> a; } void scan(long long &a) { cin >> a; } void scan(char &a) { cin >> a; } void scan(double &a) { cin >> a; } void scan(long double &a) { cin >> a; } void scan(string &a) { cin >> a; } template void scan(pair &p) { scan(p.first), scan(p.second); } template void scan(tuple &p) { scan(get<0>(p)), scan(get<1>(p)), scan(get<2>(p)); } template void scan(tuple &p) { scan(get<0>(p)), scan(get<1>(p)), scan(get<2>(p)), scan(get<3>(p)); } template void scan(vector &a) { for (auto &i: a) scan(i); } template void scan(T &a) { cin >> a; } void IN() {} template void IN(Head &head, Tail &... tail) { scan(head); IN(tail...); } vi s_to_vi(string S, char first_char = 'a') { vi A(S.size()); FOR(i, S.size()) { A[i] = S[i] - first_char; } return A; } template ostream &operator<<(ostream &os, const pair &A) { os << A.fi << " " << A.se; return os; } template ostream &operator<<(ostream &os, const tuple &t) { os << get<0>(t) << " " << get<1>(t) << " " << get<2>(t); return os; } template ostream &operator<<(ostream &os, const tuple &t) { os << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << " " << get<3>(t); return os; } template ostream &operator<<(ostream &os, const vector &A) { for (size_t i = 0; i < A.size(); i++) { if (i) os << " "; os << A[i]; } return os; } void print() { cout << "\n"; } template void print(Head &&head, Tail &&... tail) { cout << head; if (sizeof...(Tail)) cout << " "; print(forward(tail)...); } void YES(bool t = 1) { print(t ? "YES" : "NO"); } void NO(bool t = 1) { YES(!t); } void Yes(bool t = 1) { print(t ? "Yes" : "No"); } void No(bool t = 1) { Yes(!t); } void yes(bool t = 1) { print(t ? "yes" : "no"); } void no(bool t = 1) { yes(!t); } template vector cumsum(vector &A) { int N = A.size(); vector B(N + 1); B[0] = T(0); FOR(i, N) { B[i + 1] = B[i] + A[i]; } return B; } vc bin_count(vi &A, int size) { vc C(size); for (auto &x: A) { ++C[x]; } return C; } template vector argsort(vector &A) { vector ids(A.size()); iota(all(ids), 0); sort(all(ids), [&](int i, int j) { return A[i] < A[j] || (A[i] == A[j] && i < j); }); return ids; } ll binary_search(function check, ll ok, ll ng) { assert(check(ok)); while (abs(ok - ng) > 1) { auto x = (ng + ok) / 2; if (check(x)) ok = x; else ng = x; } return ok; } template inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); } template inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); } #define SUM(v) accumulate(all(v), 0LL) #define MIN(v) *min_element(all(v)) #define MAX(v) *max_element(all(v)) #define LB(c, x) distance((c).begin(), lower_bound(all(c), (x))) #define UB(c, x) distance((c).begin(), upper_bound(all(c), (x))) #define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end()) #line 3 "main.cpp" #line 1 "/home/maspy/library/algebra/addgroup.hpp" template struct AddGroup { using value_type = X; static constexpr X op(const X &x, const X &y) noexcept { return x + y; } static constexpr X inverse(const X &x) noexcept { return -x; } static constexpr X power(const X &x, ll n) noexcept { return n * x; } static constexpr X unit = ZERO; static constexpr bool commute = true; }; #line 2 "/home/maspy/library/ds/fenwick.hpp" template struct FenwickTree { using E = typename AbelGroup::value_type; int n; vector dat; E total; FenwickTree() : FenwickTree(0) {} FenwickTree(int n) : n(n), total(AbelGroup::unit) { assert(AbelGroup::commute); dat.assign(n, AbelGroup::unit); } FenwickTree(vc v) : n(len(v)), total(AbelGroup::unit) { assert(AbelGroup::commute); dat = v; FOR3(i, 1, n + 1) { int j = i + (i & -i); if (j <= n) dat[j - 1] = AbelGroup::op(dat[i - 1], dat[j - 1]); } } E sum(int k) { E ret = AbelGroup::unit; for (; k > 0; k -= k & -k) ret = AbelGroup::op(ret, dat[k - 1]); return ret; } E sum(int L, int R) { E pos = AbelGroup::unit; while (L < R) { pos = AbelGroup::op(pos, dat[R - 1]); R -= R & -R; } E neg = AbelGroup::unit; while (R < L) { neg = AbelGroup::op(neg, dat[L - 1]); L -= L & -L; } return AbelGroup::op(pos, AbelGroup::inverse(neg)); } E sum_all() { return total; } void add(int k, E x) { total = AbelGroup::op(total, x); for (++k; k <= n; k += k & -k) dat[k - 1] = AbelGroup::op(dat[k - 1], x); } template int max_right(F& check) { assert(f(E(0))); ll i = 0; E s = AbelGroup::unit; int k = 1; int N = len(dat) + 1; while (2 * k < N) k *= 2; while (k) { if (i + k < N && check(AbelGroup::op(s, dat[i + k - 1]))) { i += k; s = AbelGroup::op(s, dat[i - 1]); } k >>= 1; } return i; } int find_kth_element(E k) { auto check = [&](E x) -> bool { return x < k; }; return max_right(check); } void debug() { print("fenwick", dat); } }; #line 2 "/home/maspy/library/graph/base.hpp" template struct Edge { int frm, to; T cost; int id; }; template struct Graph { int N, M; using cost_type = T; using edge_type = Edge; vector edges; vector indptr; vector csr_edges; bool prepared; class OutgoingEdges { public: OutgoingEdges(const Graph* G, int l, int r) : G(G), l(l), r(r) {} const edge_type* begin() const { if (l == r) { return 0; } return &G->csr_edges[l]; } const edge_type* end() const { if (l == r) { return 0; } return &G->csr_edges[r]; } private: int l, r; const Graph* G; }; bool is_prepared() { return prepared; } constexpr bool is_directed() { return directed; } Graph() {} Graph(int N) : N(N), M(0), prepared(0) {} void add(int frm, int to, T cost = 1, int i = -1) { assert(!prepared); assert(0 <= frm && frm < N && 0 <= to && to < N); if (i == -1) i = M; auto e = edge_type({frm, to, cost, i}); edges.eb(e); ++M; } void prepare() { assert(!prepared); prepared = true; indptr.assign(N + 1, 0); for (auto&& e: edges) { indptr[e.frm + 1]++; if (!directed) indptr[e.to + 1]++; } FOR(v, N) indptr[v + 1] += indptr[v]; auto counter = indptr; csr_edges.resize(indptr.back() + 1); for (auto&& e: edges) { csr_edges[counter[e.frm]++] = e; if (!directed) csr_edges[counter[e.to]++] = edge_type({e.to, e.frm, e.cost, e.id}); } } OutgoingEdges operator[](int v) const { assert(prepared); return {this, indptr[v], indptr[v + 1]}; } void debug() { print("Graph"); if (!prepared) { print("frm to cost id"); for (auto&& e: edges) print(e.frm, e.to, e.cost, e.id); } else { print("indptr", indptr); print("frm to cost id"); FOR(v, N) for (auto&& e: (*this)[v]) print(e.frm, e.to, e.cost, e.id); } } int size() { return N; } }; #line 2 "/home/maspy/library/graph/centroid.hpp" template struct CentroidDecomposition { using edge_type = typename Graph::edge_type; using F = function; Graph& G; F f; // (E path value, edge e) -> E new_path_value int N; vector cdep; // depth in centroid tree vc sz; vc par; CentroidDecomposition( Graph& G, F f = [](int x, edge_type e) { return x + e.cost; }) : G(G), N(G.N), f(f), sz(G.N), par(G.N), cdep(G.N, -1) { build(); } int find(int v) { vc V = {v}; par[v] = -1; int p = 0; while (p < len(V)) { int v = V[p++]; sz[v] = 0; for (auto&& e: G[v]) { if (e.to == par[v] || cdep[e.to] != -1) continue; par[e.to] = v; V.eb(e.to); } } while (len(V)) { int v = V.back(); V.pop_back(); sz[v] += 1; if (p - sz[v] <= p / 2) return v; sz[par[v]] += sz[v]; } return -1; } void build() { assert(G.is_prepared()); assert(!G.is_directed()); int N = G.N; vc> st = {{0, 0}}; while (len(st)) { auto [lv, v] = st.back(); st.pop_back(); auto c = find(v); cdep[c] = lv; for (auto&& [frm, to, cost, id]: G[c]) { if (cdep[to] == -1) st.eb(lv + 1, to); } } } vc>> collect(int root, E root_val) { /* root を重心とする木において、(v, path data v) の vector を、方向ごとに集めて返す ・0 番目:root からのパスすべて(root を含む) ・i 番目:i 番目の方向 */ vc>> res = {{{root, root_val}}}; for (auto&& e: G[root]) { int nxt = e.to; if (cdep[nxt] < cdep[root]) continue; vc> dat; int p = 0; dat.eb(nxt, f(root_val, e)); par[nxt] = root; while (p < len(dat)) { auto [v, val] = dat[p++]; for (auto&& e: G[v]) { if (e.to == par[v]) continue; if (cdep[e.to] < cdep[root]) continue; par[e.to] = v; dat.eb(e.to, f(val, e)); } } res.eb(dat); res[0].insert(res[0].end(), all(dat)); } return res; } }; #line 7 "main.cpp" void solve() { LL(N, Q); Graph G(N); FOR(_, N - 1) { LL(a, b); G.add(--a, --b); } G.prepare(); using T = tuple; VEC(T, query, Q); for (auto&& [a, b, c]: query) --a; // 頂点 -> クエリ vc query_at(N); FOR(q, Q) query_at[get<0>(query[q])].eb(q); CentroidDecomposition CD(G); vi ANS(Q); FenwickTree> bit(N + 10); FOR(root, N) { auto dats = CD.collect(root, 0); FOR(i, len(dats)) { auto dat = dats[i]; // qid, v, dv vc event; for (auto&& [v, dv]: dat) { for (auto&& q: query_at[v]) { event.eb(q, v, dv); } } sort(all(event)); for (auto&& [qid, v, dv]: event) { auto [_, y, z] = query[qid]; ll add = bit.sum(0, dv + 1); ANS[qid] += (i == 0 ? add : -add); if (dv <= y) { bit.add(0, z); bit.add(y - dv + 1, -z); } } for (auto&& [qid, v, dv]: event) { auto [_, y, z] = query[qid]; if (dv <= y) { bit.add(0, -z); bit.add(y - dv + 1, +z); } } } } for (auto&& x: ANS) print(x); } signed main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << setprecision(15); ll T = 1; // LL(T); FOR(_, T) solve(); return 0; }