COCI 2022. D

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define int long long
#define mp make_pair
#define pb push_back

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

constexpr int INF = (int)1e18;
constexpr int N = (int)1e5 + 111;
constexpr int md = (int)1e9+7;
constexpr int mdPower = (int)1e9+7 - 1;
constexpr int M = (int)1e9;

mt19937 rnd(time(nullptr));

void add(int& a,int b){
    a += b; if(a >= md) a -= md;
}
void sub(int& a,int b){
    a -= b; if(a < 0) a += md;
}

struct node{
    node* l = nullptr;
    node* r = nullptr;
    int sum = 0;
    bool all = false;
    node(){}
};

struct edge{
    int to;
    int l,r;
    edge(){}
    edge(int to,int l,int r):to(to),l(l),r(r){}
};

vector<node*> roots;
vector<edge> g[N];
int ans[N];
int id[N];

void upd(node* v,int l,int r,int tl,int tr){
    if(l > r || tl > tr)
        return;
    if(v->all == true)
        return;
    if(l == tl && r == tr){
        v->all = true;
        v->sum = r - l + 1;
        return;
    }
    int m = (l+r)>>1;
    node* L = new node();
    if(v->l != nullptr){
        L->all = (v->l)->all;
        L->sum = (v->l)->sum;
        L->l = (v->l)->l;
        L->r = (v->l)->r;
    }
    v->l = L;
    upd(L,l,m,tl,min(tr,m));
    node* R = new node();
    if(v->r != nullptr){
        R->all = (v->r)->all;
        R->sum = (v->r)->sum;
        R->l = (v->r)->l;
        R->r = (v->r)->r;
    }
    v->r = R;
    upd(R,m+1,r,max(m+1,tl),tr);
    v->sum = (v->l)->sum + (v->r)->sum;
    return;
}

void dfs(int v,node* rt,int pr = -1){
    ans[v] = rt->sum;
    for(auto& e : g[v]){
        int& to = e.to;
        if(to == pr)
            continue;
        int& l = e.l, r = e.r;
        node* nxt_rt = new node();
        nxt_rt->all = rt->all;
        nxt_rt->l = rt->l;
        nxt_rt->r = rt->r;
        nxt_rt->sum = rt->sum;
        upd(nxt_rt,1,M,l,r);
        dfs(to,nxt_rt,v);
    }
    return;
}

void solve(){
    int n,m;
    cin >> n >> m;

    for(int i = 0; i < n-1; i++){
        int a,b,l,r;
        cin >> a >> b >> l >> r;
        g[a].pb(edge(b,l,r));
        g[b].pb(edge(a,l,r));
    }

    node* rt = new node();
    dfs(1,rt);

    for(int i = 2; i <= n; i++)
        cout << ans[i] << "\n";

    return;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    int tests = 1;
//    cin >> tests;
    for(int test = 1; test <= tests; test++){
        solve();
    }
    return 0;
}
/**

aaabbb

**/