1296F - Berland Beauty - CodeForces Solution

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

#define ll int
#define FOR(i,l,r) for(ll i = l; i <= r; ++i)
#define FOD(i,r,l) for(ll i = r; i >= l; --i)
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'
const ll inf = 1e18;
const ll N = 5000;

ll n, q, val[N + 5][N + 5];
vector<ll> dsk[N + 5];
ll par[N + 5][N + 5];
vector<ii> edge;

void dfs(ll u, ll p, ll x) {
    for(auto v : dsk[u]) {
        if(v != p) {
            par[x][v] = u;
            dfs(v,u, x);
        }
    }
}

struct jelly{
    ll a, b, g;
} p[N + 5];

bool cmp(jelly x, jelly y) {
    return x.g < y.g;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    FOR(i,1,n - 1) {
        ll u, v; cin >> u >> v;
        dsk[u].push_back(v);
        dsk[v].push_back(u);
        edge.push_back({u,v});
    }
    FOR(i,1,n) dfs(i, -1, i);
    FOR(i,1,n) FOR(j,1,n) val[i][j] = 1;
    cin >> q;
    FOR(i,1,q) {
        cin >> p[i].a >> p[i].b >> p[i].g;
    }
    sort(p + 1, p + q + 1, cmp);

    FOR(i,1,q) {
        ll u = p[i].a, v = p[i].b, w = p[i].g;
        while(u != v) {
            ll pos = par[u][v];
            val[pos][v] = val[v][pos] = w;
            v = pos;
        }
    }

    FOR(i,1,q) {
        ll minn = 1e18;
        ll w= p[i].g;
        ll u = p[i].a, v = p[i].b;
        while(u != v) {
            ll pos = par[u][v];
            minn = min(minn, val[pos][v]);
            v = pos;
        }
        if(minn != p[i].g) {
            cout << "-1";
            return 0;
        }
    }
    for(auto i : edge) {
        cout << val[i.fi][i.se] << " ";
    }
    return 0;
}
//Jelly1010