大红大紫大绿大黑

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=2e4+10,M=1e4+10;
int h[N],e[N*2],ne[N*2],w[N*2],idx;
int dep[N],son[N],sz[N],fa[N],top[N],id[N],cnt;
vector<int>ans;
bool cmp(int a,int b){
    return a>b;
}
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
struct knight{
	int f,p;
}k[N];
int n,m,q,s;
void dfs_son(int u,int f,int d){
    dep[u]=d,sz[u]=1,fa[u]=f;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==f)continue;
        dfs_son(j,u,d+1);
        sz[u]+=sz[j];
        if(sz[son[u]]<sz[j])son[u]=j;
    }
}
void dfs(int u,int t){
    top[u]=t,id[u]=++cnt;
    if(!son[u])return;
    dfs(son[u],t);
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==son[u]||j==fa[u])continue;
        dfs(j,j);
    }
}
struct node{
    int l,r,sz;
    vector<int>kn;
}tr[N*4];
void pushup(int u){
    tr[u].kn.clear();
    tr[u].sz=tr[u<<1].sz+tr[u<<1|1].sz;
    for(int i=0;i<tr[u<<1].sz;i++){
        if(tr[u<<1].kn[i]!=-1)tr[u].kn.push_back(tr[u<<1].kn[i]);
    }
    for(int i=0;i<tr[u<<1|1].sz;i++){
        if(tr[u<<1|1].kn[i]!=-1)tr[u].kn.push_back(tr[u<<1|1].kn[i]);
    }
}
void build(int u,int l,int r){
    tr[u]={l,r,0};
    if(l==r)return;
    int mid=(l+r)>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    pushup(u);
}
void modify(int u,int pos,int k,int f){
    if(tr[u].l==tr[u].r&&tr[u].l==pos){
        if(f)tr[u].kn.push_back(k),tr[u].sz++;
        else{
            for(int i=0;i<tr[u].sz;i++){
                if(tr[u].kn[i]==k){
                    tr[u].kn[i]=tr[u].kn[tr[u].sz-1];
                    tr[u].kn[tr[u].sz-1]=0;
                    return;
                }
            }
            tr[u].sz--;
        }
        return;
    }
    int mid=(tr[u].l+tr[u].r)>>1;
    if(pos<=mid)modify(u<<1,pos,k,f);
    else modify(u<<1|1,pos,k,f);
    pushup(u);
}
void query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r){
        for(int i=0;i<tr[u].sz;i++){
            ans.push_back(tr[u].kn[i]);
        }
        return;
    }
    int mid=(tr[u].l+tr[u].r)>>1;
    if(l<=mid)query(u<<1,l,r);
    if(r>mid)query(u<<1|1,l,r);
}
void query_path(int u,int v){
    ans.clear();
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        query(1,id[top[u]],id[u]);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    query(1,id[v],id[u]);
}
int main(){
	memset(h,-1,sizeof h);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		add(a,b),add(b,a);
	}
	dfs_son(1,-1,1);
	dfs(1,1);
	build(1,1,n);
	cin>>m;
	for(int i=1;i<=m;i++){
		int a,p;
		cin>>a>>p;
		k[i]={a,p};
		modify(1,id[p],a,1);
	}
	cin>>q>>s;
	int op,u,v;
	for(int i=1;i<=q;i++){
		cin>>op>>u>>v;
		if(op==1){
		    ans.clear();
			query_path(u,v);
			if(!ans.size())cout<<-1<<'\n';
			else{
			    sort(ans.begin(),ans.end(),cmp);
        		for(int i=0;i<s;i++){
        		    if(ans[i]==0||ans[i]==-1)break;
        		    cout<<ans[i]<<' ';
        		}
        		cout<<'\n';
			}
		}
		if(op==2){
		    modify(1,id[k[u].p],k[u].f,0);
		    modify(1,id[v],k[u].f,1);
			k[u].p=v;
		}
		if(op==3){
		    modify(1,id[k[u].p],k[u].f,0);
		    modify(1,id[k[u].p],v,1);
			k[u].f=v;
		}
	}
	return 0;
}