//#define _GLIBCXX_DEBUG #include using namespace std; #define endl '\n' #define lfs cout<= (ll)(n); i--) using ll = long long; using ld = long double; const ll MOD1 = 1e9+7; const ll MOD9 = 998244353; const ll INF = 1e18; using P = pair; templatebool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;} templatebool chmax(T1 &a,T2 b){if(avoid ans(bool x,T1 y,T2 z){if(x)cout<void debug(vector>&v,ll h,ll w){for(ll i=0;i&v,ll h,ll w){for(ll i=0;ivoid debug(vector&v,ll n){if(n!=0)cout<vector>vec(ll x, ll y, T w){vector>v(x,vector(y,w));return v;} ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;} vectordx={1,-1,0,0,1,1,-1,-1};vectordy={0,0,1,-1,1,-1,1,-1}; templatevector make_v(size_t a,T b){return vector(a,b);} templateauto make_v(size_t a,Ts... ts){return vector(a,make_v(ts...));} templateostream &operator<<(ostream &os, const pair&p){return os << p.first << " " << p.second;} templateostream &operator<<(ostream &os, const vector &v){for(auto &z:v)os << z << " ";cout<<"|"; return os;} //mt19937 mt(chrono::steady_clock::now().time_since_epoch().count()); struct edge{ ll to=-1; edge(){}; edge(ll t):to(t){}; }; struct CentroidDecomposition{ ll n; const vector> &g; vector used;//既に重心として選ばれたか vector sub;//部分木のサイズ CentroidDecomposition(const vector> &g):g(g){ n = g.size(); sub.assign(g.size(), 0); used.assign(g.size(), false); } ll search_centroid(ll root){ return dfs_search(root, -1, dfs_sz(root, -1) / 2 ); } ll dfs_sz(ll k, ll par){ sub[k] = 1; for(auto e:g[k]){ if(e.to == par || used[e.to])continue; sub[k] += dfs_sz(e.to, k); } return sub[k]; } ll dfs_search(ll k, ll par, ll mid){ for(auto e:g[k]){ if(e.to == par || used[e.to])continue; if(sub[e.to] > mid)return dfs_search(e.to, k, mid); } return k; } vector centroid_enum(ll root){ vectorret; ret.push_back(search_centroid(root)); for(auto e:g[ret[0]]){ if(used[e.to] || n != 2 * sub[e.to])continue; ll c = search_centroid(e.to); if(c != ret[0]){ ret.push_back(c); break; } } return ret; } vector>belong; vectorpr; void build_all(){ belong.resize(n);pr.resize(n); build(0,0); } void build(ll root,ll num){ ll cent = search_centroid(root); used[cent] = true; pr[cent]=num; build_dfs(cent, -1, cent); for(auto e:g[cent])if(!used[e.to])build(e.to,num+1); used[cent] = false; } void build_dfs(ll k,ll par,ll cent){ belong[k].push_back(cent); for(auto e:g[k]){ if(e.to == par || used[e.to])continue; build_dfs(e.to, k, cent); } } void run(){ //何か前処理を書くなら solve(0); } void solve(ll root){ ll cent = search_centroid(root); ll size = sub[root]; used[cent] = true; vector>ver; for(auto e:g[cent]){ if(!used[e.to]){ ver.emplace_back(); dfs(e.to,-1,ver.back()); } } for(auto e:g[cent]){ if(!used[e.to]){ solve(e.to); } } used[cent] = false; return; } void dfs(ll k,ll par,vector&ver){ ver.push_back(k); for(auto e:g[k]){ if(e.to==par||used[e.to])continue; dfs(e.to,k,ver); } } }; template struct BIT{ ll n; ll k=1; vectordata; BIT() = default; BIT(ll size):n(size){ n++; data.assign(n,0); while(k*2<=n)k*=2; } void add(ll a,T w){ for(ll i=a+1;i<=n;i+=i&-i)data[i-1]+=w; } void add(ll l,ll r,T w){ add(l,w);add(r+1,-w); } T sum(ll a){ if(a<0)return 0; T ret = 0; for(ll i=a+1;i>0;i-=i&-i)ret+=data[i-1]; return ret; } T sum(ll a,ll b){return a>b?0:sum(b)-sum(a-1);} T operator[](ll pos){ return sum(pos,pos); } ll lower_bound(ll x){ ll ret=0; for(ll i=k;i>0;i/=2){ if(ret+i<=n&&data[ret+i-1]>n>>q; vector>g(n); rep(i,0,n-1){ ll u,v;cin>>u>>v;u--;v--; g[u].EB(v); g[v].EB(u); } CentroidDecomposition cent(g); cent.build_all(); vector>bit(n);//距離順に並べたなにか vector>>bit2(n);//距離順に並べたなにか using TP=tuple; vector>b(n);//(所属重心、方向、距離、BIT1のindex,BIT2のindex) vector>>r(n);//[重心][方向][距離]=(BIT2上の範囲) vector>p(n);//[重心][距離]=(BIT上の範囲) auto &pr=cent.pr; rep(i,0,n){ ll time=0; vectort; using TT=tuple; //(頂点、方向、距離、親) queueque; que.emplace(i,-1,0,-1); while(!que.empty()){ auto [v,dir,d,par]=que.front(); que.pop(); if(p[i].size()<=d)p[i].EB(time,time); else p[i][d].se=time; if(dir!=-1){ if(r[i][dir].size()<=d)r[i][dir].EB(t[dir],t[dir]); else r[i][dir][d].se=t[dir]; b[v].EB(i,dir,d,time,t[dir]); t[dir]++; } else b[v].EB(i,dir,d,time,-1); time++; for(auto e:g[v]){ if(e.to==par||pr[i]>pr[e.to])continue; if(par==-1){ r[i].emplace_back(1); t.push_back(0); que.emplace(e.to,++dir,d+1,v); } else que.emplace(e.to,dir,d+1,v); } } bit[i]=BIT(time); bit2[i].resize(t.size()); rep(j,0,t.size())bit2[i][j]=BIT(t[j]); //debug(t,t.size()); //debug(p[i],p[i].size()); //debug(r[i],r[i].size()); } while(q--){ ll x,y,z;cin>>x>>y>>z;x--; ll ret=0; for(auto [c,dir,d,idx1,idx2]:b[x]){ ret+=bit[c].sum(idx1); if(dir!=-1)ret-=bit2[c][dir].sum(idx2); d=y-d; //cout<