#line 2 "/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp" #define _CRT_SECURE_NO_WARNINGS #pragma target("avx") #pragma optimize("O3") #pragma optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i,n) for(int i=0;i<(lint)(n);i++) #define REP(i,n) for(int i=1;i<=(lint)(n);i++) #define all(V) V.begin(),V.end() typedef long long lint; typedef unsigned long long ulint; typedef std::pair P; typedef std::pair LP; constexpr int INF = INT_MAX/2; constexpr lint LINF = LLONG_MAX/2; constexpr double eps = DBL_EPSILON; constexpr double PI=3.141592653589793238462643383279; template class prique :public std::priority_queue, std::greater> {}; template inline bool chmax(T& lhs, const U& rhs) { if (lhs < rhs) { lhs = rhs; return 1; } return 0; } template inline bool chmin(T& lhs, const U& rhs) { if (lhs > rhs) { lhs = rhs; return 1; } return 0; } inline lint gcd(lint a, lint b) { while (b) { lint c = a; a = b; b = c % b; } return a; } inline lint lcm(lint a, lint b) { return a / gcd(a, b) * b; } bool isprime(lint n) { if (n == 1)return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0)return false; } return true; } template T mypow(T a, lint b) { if (!b)return T(1); if (b & 1)return mypow(a, b - 1) * a; T memo = mypow(a, b >> 1); return memo * memo; } lint modpow(lint a, lint b, lint m) { if (!b)return 1; if (b & 1)return modpow(a, b - 1, m) * a % m; lint memo = modpow(a, b >> 1, m); return memo * memo % m; } template void printArray(std::vector& vec) { rep(i, vec.size() - 1)std::cout << vec[i] << " "; std::cout << vec.back() << std::endl; } template void printArray(T l, T r) { T rprev = r; rprev--; for (T i = l; i != rprev; i++) { std::cout << *i << " "; } std::cout << *rprev << std::endl; } #line 2 "simple.cpp" int N,Q; lint type[100010],v[100010],t[100010],l[100010]; lint ans[100010]; std::vector vec[50010],children[50010]; LP par[50010]; bool used[50010]; lint dist[50010]; void dfs(int node){ used[node]=true; for(const auto& i:vec[node]){ if(!used[i.first]){ children[node].emplace_back(i); dfs(i.first); } } } int main(){ scanf("%d %d",&N,&Q); rep(i,N-1){ lint a,b,c; scanf("%lld %lld %lld",&a,&b,&c); vec[a].emplace_back(b,c); vec[b].emplace_back(a,c); } rep(i,Q)scanf("%lld %lld %lld %lld",type+i,v+i,t+i,l+i); dfs(1); std::queue

que; rep(i,Q){ if(type[i]==1){ std::fill(dist+1,dist+N+1,LINF); que.push({v[i],0}); while(!que.empty()){ P p=que.front(); que.pop(); dist[p.first]=p.second; for(const P& j:children[p.first]){ que.push({j.first,p.second+j.second}); } } int ans=0; rep(j,i){ if(type[j]==0&&t[j]+dist[v[j]]<=t[i]&&dist[v[j]]<=l[j])ans++; } printf("%d\n",ans); } } }