感觉也是很 well-known 了吧。
对于要求 这种，我们一般是考虑连 跑拓扑排序。但是这题要求一个点向一段区间或一段区间向一个点连边，怎么办？我们会优化建图。
由于是在树上，树剖+线段树优化建图常数可能偏大，考虑倍增（或称 ST 表）优化建图。由于上面的连边操作显然有可重复贡献性，每次对一条链 连边或从一条链 连出边，把这条链拆成 两个长为 且并集为 的链，找到 ST 表上对应点连边即可。
ST 表内部下传的连边是平凡的，但是这些边并没有 表示 的意义，所以把这些边权设为 ，其他为 。
连完之后跑一遍 tarjan 求出强连通分量，如果一个强连通分量内部有一条边权为 的边，则一定无解，因为这样必然会得到形如 的限制。
否则缩点跑拓扑排序。但是有一个优化时间（以及缩点时需要的额外空间）的小 trick，那就是缩点跑出来的强连通分量编号事实上是图的一个拓扑序的逆序，而我们事实上也只需要求拓扑序，所以每个点按照所在强连通分量编号，从小到大排序即可求出对应点权。
code：
const int N=2e5+7,M=50*N,inf=0x3f3f3f3f,mod=0;
bool Mbe;
int n,m,cur,dep[N],siz[N],ans[N];
int fa[N][18],in[N][18],ot[N][18];
int idx,top,dfn[M],low[M],st[M];
int k,col[M];
bool vis[M];
pii a[N];
queue<int> q;
vector<int> E[N];
int tot,head[M];
struct node{
int to,nxt;bool cw;
}e[M<<1];
il void add(int u,int v,int w=0){
if(!u||!v){
return;
}
e[++tot]={v,head[u],w},head[u]=tot;
}
void dfs(int u,int f){
fa[u][0]=f,dep[u]=dep[f]+1;
siz[u]=1,dfn[u]=++idx;
in[u][0]=ot[u][0]=u;
rep(i,1,17){
fa[u][i]=fa[fa[u][i-1]][i-1];
in[u][i]=++cur,ot[u][i]=++cur;
add(in[u][i],in[u][i-1]);
add(in[u][i],in[fa[u][i-1]][i-1]);
add(ot[u][i-1],ot[u][i]);
add(ot[fa[u][i-1]][i-1],ot[u][i]);
if(!fa[u][i]){
break;
}
}
for(int v:E[u]){
if(v==f){
continue;
}
dfs(v,u),siz[u]+=siz[v];
}
}
il int getLca(int u,int v){
if(dep[u]<dep[v]){
swap(u,v);
}
drep(i,17,0){
if(dep[fa[u][i]]>=dep[v]){
u=fa[u][i];
}
}
if(u==v){
return u;
}
drep(i,17,0){
if(fa[u][i]!=fa[v][i]){
u=fa[u][i],v=fa[v][i];
}
}
return fa[u][0];
}
il int jump(int u,int k){
drep(i,17,0){
if((1<<i)<=k){
k-=(1<<i);
u=fa[u][i];
}
}
return u;
}
il void updateIn(int u,int v,int x){
int len=dep[u]-dep[v]+1,k=__lg(len);
add(x,in[u][k],1),add(x,in[jump(u,len-(1<<k))][k],1);
}
il void updateOt(int u,int v,int x){
int len=dep[u]-dep[v]+1,k=__lg(len);
add(ot[u][k],x,1),add(ot[jump(u,len-(1<<k))][k],x,1);
}
il void solve(int op,int u,int v,int x){
int w=getLca(u,v);
if(op==1){
updateOt(u,w,x);
updateOt(v,w,x);
}else{
updateIn(u,w,x);
updateIn(v,w,x);
}
}
void tarjan(int u){
dfn[u]=low[u]=++idx;
st[++top]=u,vis[u]=1;
go(i,u){
int v=e[i].to;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(vis[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
k++;
do{
int v=st[top];
col[v]=k;
vis[v]=0;
}while(st[top--]!=u);
}
}
void Yorushika(){
scanf("%d%d",&n,&m),cur=n;
rep(i,1,n-1){
int u=read(),v=read();
E[u].eb(v),E[v].eb(u);
}
dfs(1,0);
rep(i,1,m){
int op=read(),u=read(),v=read(),x=read();
if(dfn[u]>=dfn[x]&&dfn[u]<dfn[x]+siz[x]){
if(u!=x){
solve(op,u,jump(u,dep[u]-dep[x]-1),x);
}
}else{
solve(op,u,fa[x][0],x);
}
if(dfn[v]>=dfn[x]&&dfn[v]<dfn[x]+siz[x]){
if(v!=x){
solve(op,v,jump(v,dep[v]-dep[x]-1),x);
}
}else{
solve(op,v,fa[x][0],x);
}
}
mems(dfn,0),idx=0;
rep(i,1,cur){
if(!dfn[i]){
tarjan(i);
}
}
rep(u,1,cur){
go(i,u){
int v=e[i].to;
if(col[u]==col[v]){
if(e[i].cw){
puts("-1");
return;
}
}
}
}
rep(i,1,n){
a[i]=Mp(col[i],i);
}
sort(a+1,a+n+1);
rep(i,1,n){
ans[a[i].se]=i;
}
rep(i,1,n){
printf("%d ",ans[i]);
}
}
bool Med;
signed main(){
cerr<<(&Mbe-&Med)/1048576.0<<'\n';
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}
注意开够空间！
