#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 3 "/Users/kaage/Desktop/ProgrammingWorkspace/library/data-structure/BIT.hpp" class BIT { int n; std::vector bit; public: BIT(unsigned int n) :n(n) { bit.resize(n + 1, 0); } void add(int a, lint x) { while (a <= n) { bit[a] += x; a += a & -a; } } lint query(int a) { lint cnt = 0; while (a > 0) { cnt += bit[a]; a -= a & -a; } return cnt; } void clear() { bit.assign(n + 1, 0); } unsigned int lower_bound(int x){ int p=0,k=1; while(k*2<=n)k*=2; while(k>0){ if(p+k<=n&&bit[p+k]0){ if(p+k<=n&&bit[p+k]<=x){ x-=bit[p+k]; p+=k; } k/=2; } return p+1; } }; #line 3 "main.cpp" int N,Q; int type[500010],v[500010]; lint t[500010],l[500010]; int ans[500010]; std::vector> vec[200010],children[200010],comped[200010]; std::vector,std::pair>> queries[200010]; LP newpar[200010],repr[200010]; bool used[200010]; std::set verset; 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); } } } void compress(int node,int par,lint dist){ used[node]=true; bool use=verset.find(node)!=verset.end(); newpar[node]={par,dist}; if(use){ comped[par].emplace_back(node,dist); repr[node]={node,0}; } else repr[node]=newpar[node]; for(const auto& i:children[node]){ if(!used[i.first]){ if(use)compress(i.first,node,i.second); else compress(i.first,par,dist+i.second); } } } int main(){ freopen("tests/02_random11.txt","r",stdin); scanf("%d %d",&N,&Q); rep(i,N-1){ int a,b; lint c; scanf("%d %d %lld",&a,&b,&c); vec[a].emplace_back(b,c); vec[b].emplace_back(a,c); } rep(i,Q)scanf("%d %d %lld %lld",type+i,v+i,t+i,l+i); dfs(1); std::vector cords; std::queue,int>> que; BIT bit(2*Q); int B=sqrt(Q); for(int i=0;i=0){ queries[repr[v[j]].first].push_back({{t[j]+repr[v[j]].second,0},{0,l[j]-repr[v[j]].second}}); } } for(int j=i;j=i;j--){ if(type[j]==0){ int node=v[j]; lint time=t[j]; while(time-t[j]<=l[j]){ for(const auto& k:queries[node]){ if(time<=k.first.first)ans[k.first.second]++; } if(node==1)break; time+=newpar[node].second; node=newpar[node].first; } } else queries[v[j]].push_back({{t[j],j},{0,0}}); } } rep(i,Q){ if(type[i]==1)printf("%d\n",ans[i]); } }