全 WA 了。

#include <bits/stdc++.h>
#define il inline
using namespace std;
const int N=1e5+5,K=22;
int n,m,q,k,fa[N],de[N],siz[N],dfn[N],id[N],top[N],son[N],cnt;
int a[N],b[N];multiset<int,greater<int> > s[N];
vector<int> e[N];
il void add(int x,int y){e[x].push_back(y);}
void dfs1(int x,int fath){
    fa[x]=fath,de[x]=de[fath]+1,siz[x]=1;
    for(int y:e[x]){
        if(y==fath) continue;
        dfs1(y,x),siz[x]+=siz[y];
        if(siz[y]>siz[son[x]]) son[x]=y;
    }
}
void dfs2(int x,int t){
    dfn[x]=++cnt,id[cnt]=x,top[x]=t;
    if(son[x]) dfs2(son[x],t);
    for(int y:e[x]){
        if(y==fa[x] || y==son[x]) continue;
        dfs2(y,y);
    }
}
struct node{
    int a[K];
    il node(){memset(a,0,sizeof(a));}
}tree[N<<2];
il node merge(node x,node y){
    node z;int u=0,v=0;
    for(int i=0;i<=20;++i) z.a[i]=0;
    for(int i=0;i<k;++i){
        if(x.a[u]>=y.a[v]) z.a[i]=x.a[u++];
        else z.a[i]=y.a[v++];
    }
    return z;
}
il void pushup(int x){tree[x]=merge(tree[x<<1],tree[x<<1|1]);}
il void to(int x,int p){
    int u=0;if(!s[p].size()) return ;
    for(int i=0;i<=k;++i) tree[x].a[i]=0;
    for(auto it=s[p].begin();it!=s[p].end();++it){
        if(u>=k) break;
        tree[x].a[u]=*it,++u;
    }
}
void build(int x,int l,int r){
    if(l==r){to(x,id[l]);return ;}
    int mid=(l+r)>>1;
    build(x<<1,l,mid),build(x<<1|1,mid+1,r);
    pushup(x);
}
void update(int x,int l,int r,int p){
    if(l==r){to(x,id[l]);return ;}
    int mid=(l+r)>>1;
    if(p<=mid) update(x<<1,l,mid,p);
    else update(x<<1|1,mid+1,r,p);
    pushup(x);
}
node query(int x,int l,int r,int L,int R){
    if(l>=L && r<=R) return tree[x];
    int mid=(l+r)>>1;
    if(L>mid) return query(x<<1|1,mid+1,r,L,R);
    else if(R<=mid) return query(x<<1,l,mid,L,R);
    else return merge(query(x<<1,l,mid,L,R),query(x<<1|1,mid+1,r,L,R));
}
il int lca(int x,int y){
    while(top[x]!=top[y]){
        if(de[top[x]]<de[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    return de[x]<de[y]?x:y;
}
il int dis(int x,int y){return de[x]+de[y]-2*de[lca(x,y)];}
il int ck(int x,int y,int z){return dis(x,z)+dis(z,y)==dis(x,y);}
il node querypath(int x,int y){
    node ans;int u=x,v=y;
    for(int i=0;i<=20;++i) ans.a[i]=0;
    while(top[x]!=top[y]){
        if(de[top[x]]<de[top[y]]) swap(x,y);
        ans=merge(ans,query(1,1,n,dfn[top[x]],dfn[x])),x=fa[top[x]];
        if(!ck(u,v,x)) puts("*");
    }
    if(de[x]<de[y]) swap(x,y);
    if(!ck(u,v,x) || !ck(u,v,y)) puts("*");
    ans=merge(ans,query(1,1,n,dfn[y],dfn[x]));
    return ans;
}

int c[N],tot;
int opt,x,y,z,u,v,w;node cur;
int main(){
    freopen("P6578.in","r",stdin);
    freopen("P6578.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<n;++i) scanf("%d%d",&x,&y),add(x,y),add(y,x);
    scanf("%d",&m);
    for(int i=1;i<=m;++i) scanf("%d%d",&a[i],&b[i]),s[b[i]].insert(a[i]);
    scanf("%d%d",&q,&k);
    dfs1(1,0),dfs2(1,1),build(1,1,n);
    while(q--){
        scanf("%d%d%d",&opt,&x,&y);
        if(opt==1){
            cur=querypath(x,y),z=k;
            for(int i=0;i<k;++i) if(!cur.a[i]){z=i;break;}
            if(!z) puts("-1");
            else{for(int i=0;i<z;++i) printf("%d ",cur.a[i]);puts("");}
        }
        else if(opt==2){
            auto it=s[b[x]].find(a[x]);if(it!=s[b[x]].end()) s[b[x]].erase(it);
            s[y].insert(a[x]);
            update(1,1,n,dfn[b[x]]),update(1,1,n,dfn[b[x]=y]);
        }
        else{
            auto it=s[b[x]].find(a[x]);if(it!=s[b[x]].end()) s[b[x]].erase(it);
            s[b[x]].insert(a[x]=y);
            update(1,1,n,dfn[b[x]]);
        }
    }
    return 0;
}