#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define llint long long #define inf 1e18 #define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++) #define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++) #define chmin(x, y) (x) = min((x), (y)) #define chmax(x, y) (x) = max((x), (y)) #define mod 1000000007 using namespace std; typedef pair P; struct BIT{ int size; vector bit; BIT(){size = 0;} BIT(int s){ size = s; bit.resize(size+1); init(); } void init(){ for(int i = 1; i <= size; i++) bit[i] = 0; } llint query(int i){ llint ret = 0; while(i > 0){ ret += bit[i]; i -= i&(-i); } return ret; } void add(int i, llint x){ while(i <= size){ bit[i] += x; i += i&(-i); } } }; llint n, Q; vector G[100005]; llint x[100005], y[100005], z[100005]; vector qvec[100005]; llint size[200005], depth[200005]; bool used[200005]; llint ans[200005]; BIT bit(100005); int sizedfs(int v, int pre) { int ret = 1; for(int i = 0; i < G[v].size(); i++){ if(G[v][i] == pre) continue; if(used[G[v][i]]) continue; ret += sizedfs(G[v][i], v); } return size[v] = ret; } int centdfs(int v, int pre, int sz) { for(int i = 0; i < G[v].size(); i++){ if(G[v][i] == pre) continue; if(used[G[v][i]]) continue; if(size[G[v][i]] > sz/2) return centdfs(G[v][i], v, sz); } return v; } vector

vec; vector vvec[100005], gvvec[100005]; void finddfs(int v, int p, int d) { depth[v] = d; vvec[d].push_back(v); for(int i = 0; i < qvec[v].size(); i++) vec.push_back(P(depth[v], qvec[v][i])); for(int i = 0; i < G[v].size(); i++){ if(G[v][i] == p) continue; if(used[G[v][i]]) continue; finddfs(G[v][i], v, d+1); } } void calc(vector vvec[], vector

vec[], vector

vec2[], llint dep) { for(int i = 0; i <= dep; i++){ for(int j = 0; j < vec[i].size(); j++){ //cout << "+ " << vec[i][j].first << " " << vec[i][j].second << endl; bit.add(vec[i][j].first, vec[i][j].second); } for(int j = 0; j < vvec[i].size(); j++){ llint v = vvec[i][j]; //cout << i << " " << v << endl; for(int k = 0; k < qvec[v].size(); k++){ ans[qvec[v][k]] += bit.query(qvec[v][k]-1); } } for(int j = 0; j < vec2[i].size(); j++){ //cout << "- " << vec2[i][j].first << " " << vec2[i][j].second << endl; bit.add(vec2[i][j].first, vec2[i][j].second); } } } vector

global[100005], global2[100005]; vector

local[100005], local2[100005]; void solve(int v) { sizedfs(v, -1); v = centdfs(v, -1, size[v]); sizedfs(v, -1); //cout << v << endl; /* 処理 */ for(int i = 0; i <= size[v]; i++){ global[i].clear(), global2[i].clear(); gvvec[i].clear(); } for(int i = 0; i < G[v].size(); i++){ if(used[G[v][i]]) continue; vec.clear(); for(int j = 0; j <= size[G[v][i]]; j++){ local[j].clear(), local2[j].clear(); vvec[j].clear(); } finddfs(G[v][i], v, 1); for(int j = 0; j < vec.size(); j++){ llint qid = vec[j].second; if(vec[j].first > y[qid]) continue; llint dep = min(size[v], y[qid]-vec[j].first); global[0].push_back(P(qid, z[qid])); global2[dep].push_back(P(qid, -z[qid])); if(dep >= 1){ dep = min(dep, size[G[v][i]]); local[1].push_back(P(qid, -z[qid])); local2[dep].push_back(P(qid, z[qid])); } } calc(vvec, local, local2, size[G[v][i]]); for(int j = 0; j <= size[G[v][i]]; j++){ for(int k = 0; k < vvec[j].size(); k++){ gvvec[j].push_back(vvec[j][k]); } } } gvvec[0].push_back(v); for(int i = 0; i < qvec[v].size(); i++){ llint qid = qvec[v][i], dep = min(size[v], y[qid]); global[0].push_back(P(qid, z[qid])); global2[dep].push_back(P(qid, -z[qid])); } calc(gvvec, global, global2, size[v]); used[v] = true; for(int i = 0; i < G[v].size(); i++){ if(used[G[v][i]]) continue; solve(G[v][i]); } } int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> Q; llint u, v; for(int i = 1; i <= n-1; i++){ cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } for(int i = 1; i <= Q; i++){ cin >> x[i] >> y[i] >> z[i]; qvec[x[i]].push_back(i); } solve(1); for(int i = 1; i <= Q; i++) cout << ans[i] << "\n"; flush(cout); return 0; }