#include <bits/stdc++.h> #define fi first #define se second using namespace std; typedef pair<int,int> pii; typedef pair<int,pii> piii; const int MAXN = 1e5+5; int N, M, S, X, Y, L, R, ans[MAXN], A[MAXN*2], mn[MAXN*8], cnt[MAXN*8], lz[MAXN*8]; set <int> st; map <int,int> mp; vector <piii> adj[MAXN]; void join(int t) { mn[t] = min(mn[t*2],mn[t*2+1]); cnt[t] = 0; if (mn[t*2] == mn[t]) { cnt[t] += cnt[t*2]; } if (mn[t*2+1] == mn[t]) { cnt[t] += cnt[t*2+1]; } } // mn[t] = min(freq[l..r]) // cnt[t] = number of l <= i <= r : freq[i] = mn[t] void build(int t,int l,int r) { if (l == r) { mn[t] = 0; cnt[t] = A[l]; return; } int m = (l+r)/2; build(t*2,l,m); build(t*2+1,m+1,r); join(t); } void prop(int t) { if (lz[t] == 0) return; mn[t*2] += lz[t]; lz[t*2] += lz[t]; mn[t*2+1] += lz[t]; lz[t*2+1] += lz[t]; } // for all x <= i <= y : mn[i] += z; void update(int t,int l,int r,int x,int y,int z) { if (l > y || r < x) return; if (l >= x && r <= y) { mn[t] += z; lz[t] += z; return; } prop(t); int m = (l+r)/2; update(t*2,l,m,x,y,z); update(t*2+1,m+1,r,x,y,z); join(t); } void dfs(int now,int par) { ans[now] = M+1-cnt[1]; for (piii next : adj[now]) { if (next.fi == par) continue; update(1,1,S-1,mp[next.se.fi]+1,mp[next.se.se],1); dfs(next.fi,now); update(1,1,S-1,mp[next.se.fi]+1,mp[next.se.se],-1); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> M; st.insert(0); st.insert(M+1); for (int i=1;i<N;i++) { cin >> X >> Y >> L >> R; adj[X].push_back({Y,{L,R+1}}); adj[Y].push_back({X,{L,R+1}}); st.insert(L); st.insert(R+1); } S = st.size(); int i = 0; for (int x : st) { mp[x] = i; A[i] = x; i++; } for (int i=S-1;i>=1;i--) { A[i] -= A[i-1]; } build(1,1,S-1); dfs(1,1); for (int i=2;i<=N;i++) { cout << ans[i] << "\n"; } }