Contest1334/D.cpp

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 100010, maxh=40;
struct node{
    int deep, home, father;
};
int home[maxh];
node tree[maxn];
int buildTree(int s){
    if(s==1||tree[s].deep!=0){
        return tree[s].deep;
    }
    return tree[s].deep = buildTree(tree[s].father)+1;
} 
void find(int u, int v){
    home[tree[u].home]=1, home[tree[v].home]=1;
    if(tree[u].deep<tree[v].deep)
        swap(u, v);
    int differ = tree[u].deep-tree[v].deep;
    for(int i=1; i<=differ; i++){
        u = tree[u].father;
        home[tree[u].home]=1;
    }
    if(u==v)
        return;
    while(u!=v){
        u = tree[u].father;
        home[tree[u].home]=1;
        v = tree[v].father;
        home[tree[v].home]=1;
    }
}
int main(){
    int T, kase=1, n, m, q, u, v;
    cin>>T;
    while(kase<=T){
        memset(tree, 0, sizeof(tree));
        cout<<"Case "<<kase++<<":"<<endl; 
        cin>>n>>m>>q;
        for(int i=1; i<=n; i++)
            cin>>tree[i].home;
        for(int i=1; i<n; i++){
            cin>>u>>v;
            tree[v].father=u;
        }
        for(int i=1; i<=n; i++)
            if(i!=1&&tree[i].deep==0) 
                tree[i].deep=buildTree(tree[i].father)+1;
        for(int i=1; i<=q; i++){
            cin>>u>>v;
            find(u, v);
            for(int i=1; i<=m; i++)
                if(home[i])
                    cout<<i<<" ";
            cout<<endl;
            memset(home, 0, sizeof(home));
        }
    }
}