1904F - Beautiful Tree - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

#define ll int
#define ld long double
#define fu(i, a, b) for(ll i = a; i < b; i++)
#define fd(i, a, b) for(ll i = a - 1; i >= b; i--)
#define fastifier ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define x first
#define y second
#define nl '\n'
#define pl pair<ll, ll>
#define siz(x) (ll)x.size()
#define bit(i, k) (i & (1 << k))
#define cbit(i) __builtin_popcountll(i)
#define fileInput freopen("milktea.inp", "r", stdin);
#define fileOutput freopen("milktea.out", "w", stdout);
#define uid(a, b) uniform_int_distribution<ll>(a, b)(rng)  
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
template<class T> bool maxi(T& a, const T& b) {
    return a < b ? a = b, 1 : 0;
}
 
template<class T> bool mini(T& a, const T& b) {
    return a > b ? a = b, 1 : 0;
}
 
const long long inf = 1e12;
const ll mod = 1e9+7;
const ll def = 2e5+2;  

ll head[def], par[def], h[def], pos[def], big[def];
vector<ll> edg[def];
 
ll dfs(ll u, ll pre){
    ll res = 1; 
    big[u] = -1;
 
    ll crr_size = 0;
    for (ll v : edg[u]){
        if (v == pre)
            continue;
 
        par[v] = u; h[v] = h[u] + 1;
        ll child_size = dfs(v, u);
 
        if (child_size > crr_size)
            big[u] = v, crr_size = child_size;
        res += child_size;
    }
 
    return res;
}
 
ll indx = 0;
void decompose(ll u, ll root, ll pre){
    head[u] = root, pos[u] = indx++;
    if (big[u] != -1)
        decompose(big[u], root, u);
    for (ll v : edg[u]){
        if (v == pre || v == big[u])
            continue;
        decompose(v, v, u);
    }
}
 
long long st[2000000];
long long lazy[2000000];

void down(ll i){
    ll v = lazy[i];
    lazy[2 * i + 1] += v;
    lazy[2 * i + 2] += v;

    st[2 * i + 1] += v;
    st[2 * i + 2] += v;

    lazy[i] = 0;
}

vector<ll> nodem;
void get(ll l, ll r, ll i){ 
    if (l == r){
        nodem.push_back(l);
        st[i] = inf;
        return; 
    }

    down(i);
    ll mid = (l + r) / 2;
    
    if (!st[i * 2 + 1])
        get(l, mid, i * 2 + 1);
    if (!st[i * 2 + 2])
        get(mid + 1, r, i * 2 + 2);
    
    st[i] = min(st[i * 2 + 1], st[i * 2 + 2]); 
}

void update(ll l, ll r, ll crr, ll ql, ll qr, ll v){
    if (qr < l || ql > r)
        return;

    if (ql <= l && qr >= r){
        st[crr] += v;
        lazy[crr] += v;
        return;
    }

    down(crr);
    ll mid = (l + r) / 2;

    update(l, mid, crr * 2 + 1, ql, qr, v);
    update(mid + 1, r, crr * 2 + 2, ql, qr, v);

    st[crr] = min(st[crr * 2 + 1], st[crr * 2 + 2]); 
}

ll n;
vector<pl> rg;
void upd(ll u, ll v, ll c, ll val){
    while (head[u] != head[v]){
        if (h[head[u]] < h[head[v]])
            swap(u, v);

        if (pos[head[u]] <= pos[c] && pos[c] <= pos[u]){
            if (pos[head[u]] < pos[c]){
                if (val != 0)
                    update(0, n - 1, 0, pos[head[u]], pos[c] - 1, val);
                rg.push_back({pos[head[u]], pos[c] - 1});
            }
            if (pos[c] < pos[u]){
                if (val != 0)
                    update(0, n - 1, 0, pos[c] + 1, pos[u], val);
                rg.push_back({pos[c] + 1, pos[u]});
            }
        }

        else{
            if (val != 0)
                update(0, n - 1, 0, pos[head[u]], pos[u], val);
            rg.push_back({pos[head[u]], pos[u]});
        }

        u = par[head[u]];
    }
 
    if (h[u] < h[v])
        swap(u, v);

    if (pos[v] <= pos[c] && pos[c] <= pos[u]){
        if (pos[v] < pos[c]){
            if (val != 0)
                update(0, n - 1, 0, pos[v], pos[c] - 1, val);
            rg.push_back({pos[v], pos[c] - 1});
        }
        if (pos[c] < pos[u]){
            if (val != 0)
                update(0, n - 1, 0, pos[c] + 1, pos[u], val);
            rg.push_back({pos[c] + 1, pos[u]});
        }
    }

    else{
        if (val != 0)
            update(0, n - 1, 0, pos[v], pos[u], val);
        rg.push_back({pos[v], pos[u]});
    }
}

struct segmentTree{
    vector<ll> st;
    vector<vector<pl>> rg;
    vector<pair<ll, pl>> sm;
    ll n;

    void _get(ll ql, ll qr, ll l, ll r, ll i){
        if (qr < l || ql > r)
            return;

        else if (l == r){
            while (siz(rg[l]) && rg[l].back().x <= qr){
                sm.push_back({rg[l].back().y, {l, rg[l].back().x}});
                rg[l].pop_back();
            }
            if (siz(rg[l]))
                st[i] = rg[l].back().x;
            else
                st[i] = inf;
            return;
        }

        ll mid = (l + r) / 2;
        if (st[i * 2 + 1] <= qr)
            _get(ql, qr, l, mid, i * 2 + 1);
        if (st[i * 2 + 2] <= qr)
            _get(ql, qr, mid + 1, r, i * 2 + 2);

        st[i] = min(st[i * 2 + 1], st[i * 2 + 2]); 
    }

    void _update(ll l, ll r, ll crr, ll i, pl v){
        if (i < l || i > r)
            return;

        if (l == r){
            rg[l].push_back(v);
            mini(st[crr], v.x);
            return;
        }

        ll mid = (l + r) / 2;

        _update(l, mid, crr * 2 + 1, i, v);
        _update(mid + 1, r, crr * 2 + 2, i, v);

        st[crr] = min(st[crr * 2 + 1], st[crr * 2 + 2]); 
    }

    segmentTree(ll _n){
        n = _n;
        st = vector<ll>(4 * n, inf);
        rg = vector<vector<pl>>(n);
    }

    void update(ll i, pl v) {_update(0, n - 1, 0, i, v);};
    void get(ll l, ll r) {_get(l, r, 0, n - 1, 0);};
};

struct dissjointset{
    vector<ll> p;
    dissjointset (ll n){
        p = vector<ll>(n, -1);
    }

    ll find(ll n){
        return p[n] < 0 ? n : p[n] = find(p[n]); 
    }

    void merge(ll u, ll v){
        if ((u = find(u)) == (v = find(v)))
            return;

        if (p[v] < p[u])
            swap(u, v);

        p[u] += p[v];
        p[v] = u;
    }
};

void solve(){
    ll m;
    cin >> n >> m;

    fu(i, 0, n - 1){
        ll u, v;
        cin >> u >> v;

        u--; v--;
        edg[u].push_back(v);
        edg[v].push_back(u);
    }

    vector<pl> bruh[n];
    segmentTree st(n);

    dfs(0, -1);
    decompose(0, 0, -1);

    ll to[n];
    fu(i, 0, n)
        to[pos[i]] = i;

    fu(i, 0, m){
        ll t, a, b, c;
        cin >> t >> a >> b >> c;

        a--; b--; c--;
        if (t == 1){
            bruh[c].push_back({a, b});
            rg.clear();
            upd(a, b, c, 1);
        }

        else
        {
            ll total = 0;
            rg.clear();
            upd(a, b, c, 0);

            fu(i, 0, siz(rg)){
                total += rg[i].y - rg[i].x + 1;
                st.update(rg[i].x, {rg[i].y, c});
            }

            update(0, n - 1, 0, pos[c], pos[c], total);
        }
    }

    fu(i, 0, n){
        if (siz(st.rg[i]))
            sort(st.rg[i].begin(), st.rg[i].end(), greater<pl>());
    }


    dissjointset dsu(n);
    bool fuck[n];

    fill_n(fuck, n, 0);
    ll res[n];

    fill_n(res, n, -1);
    fu(i, 0, n){
        get(0, n - 1, 0);
        if (siz(nodem) <= i){
            cout << -1;
            return;
        }

        ll u = to[nodem[i]];
        res[u] = i + 1;

        fu(j, 0, siz(bruh[u])){
            auto [a, b] = bruh[u][j];
            upd(a, b, u, -1);
        }

        ll l = pos[u], r = pos[u];
        if (l > 0 && fuck[l - 1]){
            l -= -dsu.p[dsu.find(l - 1)];
            dsu.merge(pos[u], pos[u] - 1);
        }

        if (r < (n - 1) && fuck[r + 1]){
            r += -dsu.p[dsu.find(r + 1)];
            dsu.merge(pos[u], pos[u] + 1);
        }

        fuck[pos[u]] = 1;
        st.sm.clear();
        st.get(l, r);

        fu(j, 0, siz(st.sm)){
            ll c1 = st.sm[j].x;
            auto [a1, b1] = st.sm[j].y;

            update(0, n - 1, 0, pos[c1], pos[c1], -(b1 - a1 + 1));
        }
    }

    fu(i, 0, n)
        cout << res[i] << ' ';
}
 
int main(){
    fastifier;
    ll t;	
    t = 1;

    while (t--)
        solve();
}