大家好，我是这个。
注意到可以树剖后线段树优化建图跑拓扑排序，但是空间复杂度 \(O(n \log^2 n)\)，大概过不了。
注意到我们只会有一个 \(\text{dfn}\) 区间不是一条重链上一段前缀的形式（跨过 \(\text{LCA}\) 的那个区间），于是对这个区间线段树优化建图，其他预处理重链后前缀优化建图，即可 \(O(n \log n)\)。
code
// Problem: F. Beautiful Tree
// Contest: Codeforces - Codeforces Round 914 (Div. 2)
// URL: https://codeforces.com/contest/1904/problem/F
// Memory Limit: 512 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
const int logn = 20;
const int maxm = 20000000;
int n, m, fa[maxn], sz[maxn], son[maxn], dep[maxn], top[maxn], nt, dfn[maxn], tim, rnk[maxn], ans[maxn], id[maxn], f[maxn][logn];
vector<int> G[maxn], pr1[maxn], pr2[maxn];
int head[maxn * 10], len, to[maxm], nxt[maxm], ind[maxn * 10];
inline void add_edge(int u, int v) {
to[++len] = v;
++ind[v];
nxt[len] = head[u];
head[u] = len;
}
int dfs(int u, int f, int d) {
fa[u] = f;
sz[u] = 1;
dep[u] = d;
int mx = -1;
for (int v : G[u]) {
if (v == f) {
continue;
}
::f[v][0] = u;
sz[u] += dfs(v, u, d + 1);
if (sz[v] > mx) {
son[u] = v;
mx = sz[v];
}
}
return sz[u];
}
void dfs2(int u, int tp) {
top[u] = tp;
dfn[u] = ++tim;
rnk[tim] = u;
if (u == tp) {
vector<int> S;
for (int x = u; x; x = son[x]) {
S.pb(x);
}
int m = (int)S.size();
for (int i = 0; i < m; ++i) {
pr1[u].pb(++nt);
pr2[u].pb(++nt);
id[S[i]] = i;
}
for (int i = 0; i < m; ++i) {
int x = S[i];
add_edge(pr1[u][i], x);
if (i) {
add_edge(pr1[u][i], pr1[u][i - 1]);
}
add_edge(x, pr2[u][i]);
if (i) {
add_edge(pr2[u][i - 1], pr2[u][i]);
}
}
}
if (!son[u]) {
return;
}
dfs2(son[u], tp);
for (int v : G[u]) {
if (!top[v]) {
dfs2(v, v);
}
}
}
int p[maxn << 2], q[maxn << 2];
void build(int rt, int l, int r) {
p[rt] = ++nt;
q[rt] = ++nt;
if (l == r) {
add_edge(p[rt], rnk[l]);
add_edge(rnk[l], q[rt]);
return;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
add_edge(p[rt], p[rt << 1]);
add_edge(p[rt], p[rt << 1 | 1]);
add_edge(q[rt << 1], q[rt]);
add_edge(q[rt << 1 | 1], q[rt]);
}
void update1(int rt, int l, int r, int ql, int qr, int u) {
if (ql <= l && r <= qr) {
add_edge(u, p[rt]);
return;
}
int mid = (l + r) >> 1;
if (ql <= mid) {
update1(rt << 1, l, mid, ql, qr, u);
}
if (qr > mid) {
update1(rt << 1 | 1, mid + 1, r, ql, qr, u);
}
}
void update2(int rt, int l, int r, int ql, int qr, int u) {
if (ql <= l && r <= qr) {
add_edge(q[rt], u);
return;
}
int mid = (l + r) >> 1;
if (ql <= mid) {
update2(rt << 1, l, mid, ql, qr, u);
}
if (qr > mid) {
update2(rt << 1 | 1, mid + 1, r, ql, qr, u);
}
}
inline void update1(int x, int y, int u) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) {
swap(x, y);
}
int v = top[x];
int t = id[x];
add_edge(u, pr1[v][t]);
x = fa[top[x]];
}
if (dep[x] > dep[y]) {
swap(x, y);
}
update1(1, 1, n, dfn[x], dfn[y], u);
}
inline void update2(int x, int y, int u) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) {
swap(x, y);
}
int v = top[x];
int t = id[x];
add_edge(pr2[v][t], u);
x = fa[top[x]];
}
if (dep[x] > dep[y]) {
swap(x, y);
}
update2(1, 1, n, dfn[x], dfn[y], u);
}
inline int qlca(int x, int y) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) {
swap(x, y);
}
x = fa[top[x]];
}
if (dep[x] > dep[y]) {
swap(x, y);
}
return x;
}
inline int jump(int u, int k) {
for (int i = 18; ~i; --i) {
if (k & (1 << i)) {
u = f[u][i];
}
}
return u;
}
inline int calc1(int x, int y) {
if (qlca(x, y) == y) {
return jump(x, dep[x] - dep[y] - 1);
} else {
return fa[y];
}
}
inline int calc2(int x, int y) {
if (qlca(x, y) == x) {
return jump(y, dep[y] - dep[x] - 1);
} else {
return fa[x];
}
}
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1, u, v; i < n; ++i) {
scanf("%d%d", &u, &v);
G[u].pb(v);
G[v].pb(u);
}
nt = n;
dfs(1, -1, 1);
dfs2(1, 1);
build(1, 1, n);
for (int j = 1; j <= 18; ++j) {
for (int i = 1; i <= n; ++i) {
f[i][j] = f[f[i][j - 1]][j - 1];
}
}
while (m--) {
int op, x, y, z;
scanf("%d%d%d%d", &op, &x, &y, &z);
if (op == 1) {
if (x != z) {
int u = calc1(x, z);
update1(x, u, z);
}
if (y != z) {
int u = calc2(z, y);
update1(u, y, z);
}
} else {
if (x != z) {
int u = calc1(x, z);
update2(x, u, z);
}
if (y != z) {
int u = calc2(z, y);
update2(u, y, z);
}
}
}
queue<int> q;
for (int i = 1; i <= nt; ++i) {
if (!ind[i]) {
q.push(i);
}
}
int cnt = 0;
while (q.size()) {
int u = q.front();
q.pop();
if (u <= n) {
ans[u] = ++cnt;
}
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (!(--ind[v])) {
q.push(v);
}
}
}
for (int i = 1; i <= nt; ++i) {
if (ind[i]) {
puts("-1");
return;
}
}
for (int i = 1; i <= n; ++i) {
printf("%d ", ans[i]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}