// #include <bits/stdc++.h> #include <iostream> #include <cmath> #include <algorithm> #include <map> #include <vector> #include <iomanip> #include <string> #include <queue> #include <set> #include <deque> #include <numeric> #include <stack> #include <chrono> using namespace std; void fast_io(){ // freopen("", "r", stdin); // freopen("", "w", stdout); ios::sync_with_stdio(0); cin.tie(); cout.tie(); cout << setprecision(9); } #define int long long #define endl '\n' #define all(v) (v).begin(), (v).end() #define rall(v) (v).rbegin(), (v).rend() #define fi first #define se second const int N = 2e5 + 5; int n, m, cur_ans; int L[N], R[N], ans[N]; vector<pair<int, pair<int, int>>> adj[N]; map<int, int> real; int dif(int x, int y){ return real[y] - real[x]; } struct node{ int s = 0, mi = 0, C = 0, lazy = 0; } T[4 * N]; node pull(node lc, node rc){ node res; if (lc.mi == rc.mi) res.C = lc.C + rc.C; else if (lc.mi < rc.mi) res.C = lc.C; else res.C = rc.C; res.mi = min(lc.mi, rc.mi); res.s = lc.s + rc.s; return res; } void push(int s, int e, int v){ int mid = (e + s) / 2, lc = 2 * v, rc = lc + 1; T[lc].mi += T[v].lazy; T[lc].s += T[v].lazy * (mid - s); T[lc].lazy += T[v].lazy; T[rc].mi += T[v].lazy; T[rc].s += T[v].lazy * (e - mid); T[rc].lazy += T[v].lazy; T[v].lazy = 0; } void update(int val, int l, int r, int s = 0, int e = n, int v = 1){ if (l >= e or s >= r) return; if (l <= s and e <= r){ T[v].mi += val; T[v].s += val * (e - s); T[v].lazy += val; return; } int mid = (e + s) / 2, lc = 2 * v, rc = lc + 1; push(s, e, v); update(val, l, r, s, mid, lc); update(val, l, r, mid, e, rc); T[v] = pull(T[lc], T[rc]); } node get(int l, int r, int s = 0, int e = n, int v = 1){ if (l <= s && e <= r){ return T[v]; } int mid = (e + s) / 2, lc = 2 * v, rc = lc + 1; push(s, e, v); if (l < mid){ node res = get(l, r, s, mid, lc); if (r > mid){ res = pull(res, get(l, r, mid, e, rc)); } return res; } return get(l, r, mid, e, rc); } void build(int s = 0, int e = n, int v = 1){ if (e - s == 1){ T[v].C = 1; return; } int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1; build(s, mid, lc); build(mid, e, rc); T[v].C = T[lc].C + T[rc].C; } void dfs(int u = 1, int par = 0, vector<pair<int, int>> cost = {}){ sort(all(cost)); vector<pair<int, int>> ch; if (cost.size()){ ch.push_back(cost[0]); for (int i = 1; i < (int) cost.size(); i++){ if (ch[i].first <= cost.back().second){ auto x = ch.back(); ch.pop_back(); x.second = max(x.second, cost[i].second); ch.push_back(x); } } } // cout << u << endl; // for (auto i : ch) cout << i.first << ' ' << i.second << endl; // cout << endl; for (int i = 0; i < (int) ch.size(); i++) ans[u] += ch[i].second - ch[i].first + 1; for (auto [v, interval] : adj[u]){ if (v == par) continue; ch.push_back({interval.first, interval.second}); dfs(v, u, ch); ch.pop_back(); } } void solve() { cin >> n >> m; swap(m, n); for (int i = 1; i < m; i++){ int u, v, l, r; cin >> u >> v >> l >> r; adj[u].push_back({v, {l, r}}); adj[v].push_back({u, {l, r}}); } build(); dfs(); for (int i = 2; i <= m; i++) cout << ans[i] << ' '; cout << endl; return; } signed main() { fast_io(); srand(chrono::steady_clock::now().time_since_epoch().count()); int tc = 1; // cin >> tc; while (tc--) solve(); return 0; }