【题目描述】：
    在一片古老的土地上，有一个繁荣的文明。
    这片大地几乎被森林覆盖，有N座城坐落其中。巧合的是，这N座城由恰好N-1条双向道路连接起来，使得任意两座城都是连通的。也就是说，这些城形成了树的结构，任意两座城之间有且仅有一条简单路径。
    在这个文明中，骑士是尤其受到尊崇的职业。任何一名骑士，都是其家族乃至家乡的荣耀。Henry从小就渴望成为一名能守护家乡、驱逐敌人的骑士。勤奋训练许多年后，Henry终于满18岁了。他决定离开家乡，向那些成名已久的骑士们发起挑战！
    根据Henry的调查，大陆上一共有M名受封骑士，不妨编号为1到M。
    第i个骑士居住在城Pi，武力值为Fi。
    Henry计划进行若干次旅行，每次从某座城出发沿着唯一的简单路径前往另一座城，同时会挑战路线上武力值最高的K个骑士（Henry的体力有限，为了提高水平，当然要挑战最强的骑士）。如果路线上的骑士不足K人，Henry会挑战遇到的所有人。
    每次旅行前，可能会有某些骑士的武力值或定居地发生变化，Henry自然会打听消息，并对计划做出调整。
    为了在每次旅行时做好充分准备，Henry希望你能帮忙在每次旅行前计算出这条路线上他将挑战哪些对手。
【题目解法】：
    考虑没有修改的情况，我们用T[x]表示root->x的主席树
    然后我们查询的时候只需要在T[x]+T[y]-T[lca(x,y))+T[fa[lca(x,y)]]这颗主席树上二分即可
    现在我们有了修改操作：考虑每次修改操作，影响到的点为子树中的点
    因此我们可以弄出dfs序，那么修改就变成了修改某一段连续点的主席树
    我们可以外层树状数组，内层线段树维护即可
    复杂度O(N log N log 1000)

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=80005;
const int M=30;
struct edge {int x,next;} b[N*2];
struct node {int lc,rc,t;} tree[N*50];
struct KnightNode {int p,x;} knight[N];
int n,m,q,rank,dfn[N],L[N],R[N],cnt,fa[21][N],dep[N];
int A[M],B[M],C[M],D[M],fight[N],ans,tot,a[N],root[N],Ans[N];
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
inline int lowbit(int x)
{
    return x&(-x);
}
inline void addedge(int x,int y)
{
    ++tot;
    b[tot].x=y;
    b[tot].next=a[x];
    a[x]=tot;
}
void init()
{
    n=getint(); cnt=0;
    for (int i=1; i<n; i++)
    {
        int x=getint(),y=getint();
        addedge(x,y); addedge(y,x);
    }
    tot=0;
}
void dfs(int x,int pre,int depth)
{
    dfn[x]=++cnt; L[x]=cnt; fa[0][x]=pre; dep[x]=depth;
    for (int p=a[x];p;p=b[p].next) if (b[p].x!=pre) dfs(b[p].x,x,depth+1);
    R[x]=cnt;
}
void modify(int &p,int l,int r,int x,int y)
{
    if (p==0) p=++tot; tree[p].t+=y;
    int mid=(l+r)/2; if (l==r) return;
    if (x<=mid) modify(tree[p].lc,l,mid,x,y);
    else modify(tree[p].rc,mid+1,r,x,y);
}
void modify(int x,int y,int flag)
{
    while (x>0) 
    {
        modify(root[x],1,1000,y,flag); 
        x-=lowbit(x);
    }
}
void modify(int l,int r,int x,int flag)
{
    modify(r,x,flag);
    modify(l-1,x,-flag);
}
void ask(int x,int now[])
{
    now[0]=0; if (x==0) return;
    while (x<=n) now[++now[0]]=root[x],x+=lowbit(x);
}
inline int LCA(int x,int y)
{
    if (dep[x]<dep[y]) swap(x,y);
    for (int j=0,k=dep[x]-dep[y];k;k/=2,j++) if (k%2==1) x=fa[j][x];
    if (x==y) return x;
    for (int i=20; i>=0; i--) if (fa[i][x]!=fa[i][y]) x=fa[i][x],y=fa[i][y];
    return fa[0][x];
}
void print(int a[],int b[],int c[],int d[],int l,int r)
{
    int A[M],B[M],C[M],D[M];
    int nowans=0;
    for (int i=1; i<=a[0]; i++) nowans+=tree[a[i]].t;
    for (int i=1; i<=b[0]; i++) nowans+=tree[b[i]].t;
    for (int i=1; i<=c[0]; i++) nowans-=tree[c[i]].t;
    for (int i=1; i<=d[0]; i++) nowans-=tree[d[i]].t;
    if (l==r) {for (int i=1; i<=nowans; i++) Ans[++cnt]=l; return;}
    if (nowans==0) return; int mid=(l+r)/2;
    for (int i=1; i<=a[0]; i++) A[i]=tree[a[i]].rc; A[0]=a[0];
    for (int i=1; i<=b[0]; i++) B[i]=tree[b[i]].rc; B[0]=b[0];
    for (int i=1; i<=c[0]; i++) C[i]=tree[c[i]].rc; C[0]=c[0];
    for (int i=1; i<=d[0]; i++) D[i]=tree[d[i]].rc; D[0]=d[0];
    print(A,B,C,D,mid+1,r);
    for (int i=1; i<=a[0]; i++) A[i]=tree[a[i]].lc; A[0]=a[0];
    for (int i=1; i<=b[0]; i++) B[i]=tree[b[i]].lc; B[0]=b[0];
    for (int i=1; i<=c[0]; i++) C[i]=tree[c[i]].lc; C[0]=c[0];
    for (int i=1; i<=d[0]; i++) D[i]=tree[d[i]].lc; D[0]=d[0];
    print(A,B,C,D,l,mid);
}
void ask(int l,int r,int k)
{
    int nowans=0; int mid=(l+r)/2;
    for (int i=1; i<=A[0]; i++) nowans+=tree[tree[A[i]].rc].t;
    for (int i=1; i<=B[0]; i++) nowans+=tree[tree[B[i]].rc].t;
    for (int i=1; i<=C[0]; i++) nowans-=tree[tree[C[i]].rc].t;
    for (int i=1; i<=D[0]; i++) nowans-=tree[tree[D[i]].rc].t;
    if (l==r) 
    {
        nowans=0;
        for (int i=1; i<=A[0]; i++) nowans+=tree[A[i]].t;
        for (int i=1; i<=B[0]; i++) nowans+=tree[B[i]].t;
        for (int i=1; i<=C[0]; i++) nowans-=tree[C[i]].t;
        for (int i=1; i<=D[0]; i++) nowans-=tree[D[i]].t;
        for (int i=1; i<=min(k,nowans); i++) Ans[++cnt]=l; return;
    }
    if (k<=nowans)
    {
        for (int i=1; i<=A[0]; i++) A[i]=tree[A[i]].rc;
        for (int i=1; i<=B[0]; i++) B[i]=tree[B[i]].rc;
        for (int i=1; i<=C[0]; i++) C[i]=tree[C[i]].rc;
        for (int i=1; i<=D[0]; i++) D[i]=tree[D[i]].rc;
        ask(mid+1,r,k);
    }
    else
    {
        int a[M],b[M],c[M],d[M];
        for (int i=1; i<=A[0]; i++) a[i]=tree[A[i]].rc; a[0]=A[0];
        for (int i=1; i<=B[0]; i++) b[i]=tree[B[i]].rc; b[0]=B[0];
        for (int i=1; i<=C[0]; i++) c[i]=tree[C[i]].rc; c[0]=C[0];
        for (int i=1; i<=D[0]; i++) d[i]=tree[D[i]].rc; d[0]=D[0];
        print(a,b,c,d,mid+1,r);
        for (int i=1; i<=A[0]; i++) A[i]=tree[A[i]].lc;
        for (int i=1; i<=B[0]; i++) B[i]=tree[B[i]].lc;
        for (int i=1; i<=C[0]; i++) C[i]=tree[C[i]].lc;
        for (int i=1; i<=D[0]; i++) D[i]=tree[D[i]].lc;
        ask(l,mid,k-nowans);
    }
}
void query(int x,int y,int k)
{
    int K=LCA(x,y);
    ask(dfn[x],A); ask(dfn[y],B); ask(dfn[K],C); ask(dfn[fa[0][K]],D);
    cnt=0; ask(1,1000,k); if (cnt==0) {printf("%d\n",-1); return;}
    for (int i=1; i<=cnt; i++) printf("%d ",Ans[i]); printf("\n");
}
void prepare()
{
    for (int i=1; i<=20; i++)
        for (int j=1; j<=n; j++)
        fa[i][j]=fa[i-1][fa[i-1][j]];
    m=getint();
    for (int i=1; i<=m; i++)
    {
        knight[i].x=getint(); knight[i].p=getint(); fight[knight[i].x]++;
        modify(L[knight[i].p],R[knight[i].p],knight[i].x,1);
    }
}
void solve()
{
    q=getint(); rank=getint();
    for (int i=1; i<=q; i++)
    {
        int opt=getint(),x=getint(),y=getint();
        if (opt==1) query(x,y,rank);
        if (opt==2)
        {
            modify(L[knight[x].p],R[knight[x].p],knight[x].x,-1);
            knight[x].p=y;
            modify(L[knight[x].p],R[knight[x].p],knight[x].x,1);
        }
        if (opt==3)
        {
            modify(L[knight[x].p],R[knight[x].p],knight[x].x,-1);
            knight[x].x=y; fight[knight[x].x]--; fight[y]++;
            modify(L[knight[x].p],R[knight[x].p],knight[x].x,1);
        }
    }
}
int main()
{
    init();
    dfs(1,0,1);
    prepare();
    solve();
    return 0;
}