1957F1 - Frequency Mismatch (Easy Version)

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;

const int N = 2e5+5, LOG = 17, MOD = 1000000007;
mt19937 eng{std::random_device{}()};

int rnd(){
    uniform_int_distribution<int> uid(0, MOD-1);
    return uid(eng) % MOD;
}

const int R = rnd();

long long power(long long a, long long b, long long m=MOD) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res % m;
}

int inv(int a){
    return power(a,MOD-2);
}

int n,q,k,ar[N],st[N],en[N],ord[N],d[N],p[LOG][N],cnt;
vector<vector<int> > e;
vector<int> res;

void dfs(int node,int prnt){
    st[node] = ++cnt;
    ord[cnt] = node;
    p[0][node] = prnt;
    for(int i = 1;i<LOG;i++){
        p[i][node] = p[i-1][p[i-1][node]];
    }
    for(auto nxt:e[node]){
        if(nxt == prnt)
            continue;
        d[nxt] = d[node] + 1;
        dfs(nxt,node);
    }
    en[node] = ++cnt;
    ord[cnt] = node;
}
int getKth(int a,int K){
    for(int i = 0;i<LOG;i++){
        if((1<<i) & K){
            a = p[i][a];
        }
    }
    return a;
}
int LCA(int a,int b){
    if(d[a] < d[b])
        swap(a,b);
    a = getKth(a,d[a]-d[b]);
    if(a == b)
        return a;
    for(int i = LOG-1;i>=0;i--){
        if(p[i][a] != p[i][b]){
            a = p[i][a];
            b = p[i][b];
        }
    }
    return p[0][a];
}

extern struct Node *EMPTY;

struct Node{
    ll mul;
    Node *lt,*rt;
    Node(){
        lt = this;
        rt = this;
        mul = 1LL;
    }
    Node(ll mull,Node *ltt = EMPTY,Node *rtt = EMPTY){
        mul  = mull;
        lt = ltt;
        rt = rtt;
    }
    // Node():lt(this),rt(this),mul(1LL){}
    // Node(ll mul,Node *lt = EMPTY, Node *rt = EMPTY):mul(mul),lt(lt),rt(rt){}
};
Node *EMPTY = new Node();
Node *roots[N];

Node *insert(int val,Node *cur,int neg = 0,int l = 1,int r = 1e5){
    if(val > r || val < l)
        return cur;
    if(l == r){
        if(neg){
            return new Node(cur->mul * inv((R + val + 0LL) % MOD) % MOD);
        }
        return new Node(cur->mul * ((R + val + 0LL) % MOD) % MOD);
    }
    int md = (l+r)/2;
    Node *LT = insert(val,cur->lt,neg,l,md);
    Node *RT = insert(val,cur->rt,neg,md+1,r);
    return new Node(LT->mul * RT->mul % MOD,LT,RT);
}

ll calcMul(Node *lft,Node *rgt){
    return rgt->mul * inv(lft->mul) % MOD;
}
ll calcMul(Node *downLft1,Node *downRgt1,Node *upLft1,Node *upRgt1,ll lca1,int l,int r){
    ll mul = inv(calcMul(downLft1,downRgt1)) * calcMul(upLft1,upRgt1) % MOD;
    if(lca1 >= l && lca1 <= r){
        // cout<<"H"<<lca1<<"H ";
        mul = mul * ((lca1 + R + 0LL) % MOD) % MOD;
    }
    return mul;
}

void traverse(Node *cur,int l = 1,int r = 1e5){
    cout<<l<<" "<<r<<" "<<cur->mul<<endl;
    if(l == r){
        return;
    }
    int md = (l+r)/2;
    traverse(cur->lt,l,md);
    traverse(cur->rt,md+1,r);
}
void print(){
    for(int i = 0;i<=cnt;i++){
        cout<<i<<":\n";
        traverse(roots[i]);
        cout<<endl;
    }
}
void query(Node *downLft1,Node *downLft2,Node *downRgt1,Node *downRgt2,Node *upLft1,Node *upLft2,Node *upRgt1,Node *upRgt2,ll lca1,ll lca2,int l = 1,int r = 1e5){
    if(l == r){
        res.push_back(l);
        return;
    }
    int md = (l + r) / 2;
    ll frstMul = calcMul(downLft1->lt,downRgt1->lt,upLft1->lt,upRgt1->lt,lca1,l,md);
    ll scndMul = calcMul(downLft2->lt,downRgt2->lt,upLft2->lt,upRgt2->lt,lca2,l,md);
    // cout<<l<<" "<<r<<" "<<md<<" :1: "<<frstMul<<" "<<scndMul<<endl;
    if(frstMul != scndMul){
        query(downLft1->lt,downLft2->lt,downRgt1->lt,downRgt2->lt,upLft1->lt,upLft2->lt,upRgt1->lt,upRgt2->lt,lca1,lca2,l,md);
    }
    if(res.size() == k)
        return;
    frstMul = calcMul(downLft1->rt,downRgt1->rt,upLft1->rt,upRgt1->rt,lca1,md+1,r);
    scndMul = calcMul(downLft2->rt,downRgt2->rt,upLft2->rt,upRgt2->rt,lca2,md+1,r);
    // cout<<l<<" "<<r<<" "<<md<<" :2: "<<frstMul<<" "<<scndMul<<endl;
    if(frstMul != scndMul){
        query(downLft1->rt,downLft2->rt,downRgt1->rt,downRgt2->rt,upLft1->rt,upLft2->rt,upRgt1->rt,upRgt2->rt,lca1,lca2,md+1,r);
    }
}

int main(){

    // freopen("in.txt","r",stdin);
    scanf("%d",&n);
    for(int i = 1;i<=n;i++){
        scanf("%d",&ar[i]);
    }
    e.clear();
    e.resize(n+1);
    for(int i = 0;i<n-1;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    d[1] = 0;
    cnt = 0;
    dfs(1,0);
    roots[0] = EMPTY;
    assert(cnt == 2*n);
    for(int i = 1;i<=cnt;i++){
        if(i > st[ord[i]])
            roots[i] = insert(ar[ord[i]],roots[i-1],1);
        else
            roots[i] = insert(ar[ord[i]],roots[i-1]);
    }
    // print();
    scanf("%d",&q);
    for(int testCase = 1;testCase<=q;testCase++){
        int u1,v1,u2,v2;
        scanf("%d%d%d%d%d",&u1,&v1,&u2,&v2,&k);
        if(st[u1] > st[v1])
            swap(u1,v1);
        if(st[u2] > st[v2])
            swap(u2,v2);
        int lca1 = LCA(u1,v1),oneDown = getKth(u1,d[u1] - d[lca1] - 1),oneUp = getKth(v1,d[v1] - d[lca1] - 1);
        int lca2 = LCA(u2,v2),twoDown = getKth(u2,d[u2] - d[lca2] - 1),twoUp = getKth(v2,d[v2] - d[lca2] - 1);
        assert(lca1 >= 1 && lca1 <= n);
        assert(lca2 >= 1 && lca2 <= n);
        int lftDown1 = en[u1] - 1,rgtDown1,lftDown2 = en[u2]-1,rgtDown2;
        if(u1 == lca1){
            lftDown1 = st[u1] + 1;
            rgtDown1 = lftDown1 - 1;
        }else{
            rgtDown1 = en[oneDown];
        }
        if(u2 == lca2){
            rgtDown2 = en[u2] - 2;
        }else{
            rgtDown2 = en[twoDown];
        }
        int lftUp1,rgtUp1 = st[v1],lftUp2,rgtUp2 = st[v2];
        if(v1 == lca1){
            lftUp1 = st[v1] + 1;
        }else{
            lftUp1 = st[oneUp] - 1;
        }
        if(v2 == lca2){
            lftUp2 = st[v2] + 1;
        }else{
            lftUp2 = st[twoUp] - 1;
        }
        // cout<<u1<<" "<<v1<<" "<<lca1<<" "<<u2<<" "<<v2<<" "<<lca2<<endl;
        // cout<<lftDown1<<" "<<rgtDown1<<" "<<lftDown2<<" "<<rgtDown2<<endl;
        // cout<<lftUp1<<" "<<rgtUp1<<" "<<lftUp2<<" "<<rgtUp2<<endl;
        // cout<<endl;
        Node *downLft1,*downLft2,*downRgt1,*downRgt2,*upLft1,*upLft2,*upRgt1,*upRgt2;
        if(lftDown1 <= rgtDown1){
            downLft1 = roots[lftDown1];
            downRgt1 = roots[rgtDown1];
        }else{
            downLft1 = EMPTY;
            downRgt1 = EMPTY;
        }
        if(lftDown2 <= rgtDown2){
            downLft2 = roots[lftDown2];
            downRgt2 = roots[rgtDown2];
        }else{
            downLft2 = EMPTY;
            downRgt2 = EMPTY;
        }

        if(lftUp1 <= rgtUp1){
            upLft1 = roots[lftUp1];
            upRgt1 = roots[rgtUp1];
        }else{
            upLft1 = EMPTY;
            upRgt1 = EMPTY;
        }
        if(lftUp2 <= rgtUp2){
            upLft2 = roots[lftUp2];
            upRgt2 = roots[rgtUp2];
        }else{
            upLft2 = EMPTY;
            upRgt2 = EMPTY;
        }
        res.clear();
        query(downLft1,downLft2,downRgt1,downRgt2,upLft1,upLft2,upRgt1,upRgt2,ar[lca1],ar[lca2]);
        // cout<<"Test Case: #"<<testCase<<" "<<res.size();
        printf("%d",res.size());
        for(auto x:res){
            printf(" %d",x);
        }
        puts("");
    }
    return 0;
}