常数制造机…

Solution

考虑不重复的计算质因数。令 ${p_i}^{k_i}$ 形式的质因数成为一种颜色，贡献为 $p$ ，则最多可分割出 $n\log V$ 种颜色，现在要做的是对限定深度不重复计算颜色的贡献。

那么对深度设主席树（每一层的话是动态开点），然后对每个颜色计算树上差分进行贡献。同时对于每个颜色记录一个 set 来维护已出现 dfn 序，如果新加入了一个颜色在树上计算与 dfs 序相邻的已出现的点的贡献的变化量。查询的时候直接在主席树上查询即可。

复杂度大概是 $\log^2$ 级别？空间复杂度是玄学…

Code

// Code by ajcxsu
// Problem: half

#include<bits/stdc++.h>
#define MOD (998244353)
using namespace std;

template<typename T> inline void gn(T &x) {
    char ch=getchar(), pl=0; x=0;
    while(!isdigit(ch)) pl=ch=='-', ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0', ch=getchar(); x*=pl?-1:1;
}
template<typename T, typename ...Args> inline void gn(T &x, Args &...args) {
    gn(x), gn(args...);
}

const int K=1e7+10, N=1e5+10, OP=19;
int h[N], to[N<<1], nexp[N<<1], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }

typedef pair<int, int> mpa;
int dep[N], dl[N], dr[N], dd[N], idx;
int gup[OP][N];
void dfs(int x, int k) {
    dep[x]=k, dl[x]=++idx, dd[idx]=x;
    for(int u=h[x];u;u=nexp[u])
        if(!dep[to[u]]) {
            dfs(to[u], k+1);
            gup[0][to[u]]=x;
        }
    dr[x]=idx;
}
int lca(int s, int t) {
    if(dep[s]<dep[t]) swap(s, t);
    for(int j=OP-1; j>=0; j--) if(dep[gup[j][s]]>=dep[t]) s=gup[j][s];
    if(s==t) return s;
    for(int j=OP-1; j>=0; j--)
        if(gup[j][s]!=gup[j][t]) s=gup[j][s], t=gup[j][t];
    return gup[0][s];
}


struct Dot { int x, k, i; } ;
bool cmp(const Dot &a, const Dot &b) { return dep[a.x]<dep[b.x]; }
vector<Dot> dot;
vector<mpa> lis;
int val[N];
int pri[K], pre[K], inv[K], pp;
bool npri[K];
void di(int x, int y) {
    int k=0, rua=0;
    while(x>1) {
        if(rua!=pre[x]) rua=pre[x], k=0;
        k++;
        lis.push_back(mpa(rua, k));
        dot.push_back({y, rua, k});
        x/=rua;
    }
}

struct Node *nil;
struct Node {
    Node *ls=nil, *rs=nil;
    int v=1, t=0;
} ;
Node *nd[N];
void ini() {
    nil=new Node, nil->ls=nil->rs=nil; 
    nd[0]=nil;
}
void updata(Node *&x, int l, int r, int d, int v, int nt) {
    if(x->t!=nt) {
        Node *nd=new Node; *nd=*x, x=nd;
        x->t=nt;
    }
    x->v=1ll*x->v*v%MOD;
    if(l==r) return; int mid=(l+r)>>1;
    if(d<=mid) updata(x->ls, l, mid, d, v, nt);
    else updata(x->rs, mid+1, r, d, v, nt);
}
int query(Node *x, int l, int r, int xl, int xr) {
    if(xl<=l && r<=xr) return x->v;
    int mid=(l+r)>>1, ret=1;
    if(xl<=mid) ret=1ll*ret*query(x->ls, l, mid, xl, xr)%MOD;
    if(xr>mid) ret=1ll*ret*query(x->rs, mid+1, r, xl, xr)%MOD;
    return ret;
}

set<int> s[N*25];
int main() {
    #ifndef LOCAL
    freopen("half.in","r",stdin);
    freopen("half.out","w",stdout);
    #endif
    ini();
    ios::sync_with_stdio(false), cin.tie(0);
    /* pri inv */
    inv[1]=1; for(int i=2; i<K; i++) inv[i]=(MOD-1ll*MOD/i*inv[MOD%i]%MOD);
    npri[1]=1;
    for(int i=2; i<K; i++) {
        if(!npri[i]) pri[pp++]=i, pre[i]=i;
        for(int j=0; j<pp && i*pri[j]<K; j++) {
            npri[i*pri[j]]=1, pre[i*pri[j]]=pri[j];
            if(i%pri[j]==0) break;
        }
    }
    /* input */
    int k, n;
    gn(k), gn(n);
    int na;
    for(int i=1; i<=n; i++) {
        gn(na);
        di(na, i);
    }
    int u, v;
    for(int i=1; i<n; i++) gn(u), gn(v), ins(u, v), ins(v, u);
    /* up */
    dfs(1, 1);
    for(int j=1; j<OP; j++)
        for(int i=1; i<=n; i++)
            gup[j][i]=gup[j-1][gup[j-1][i]];
    /* lis */
    sort(lis.begin(), lis.end()); int tk=unique(lis.begin(), lis.end())-lis.begin();

    for(int i=0; i<tk; i++) val[i]=lis[i].first;
    for(Dot &x:dot)
        x.k=lower_bound(lis.begin(), lis.begin()+tk, mpa(x.k, x.i))-lis.begin();
    sort(dot.begin(), dot.end(), cmp);
    /* add */
    int j=0;
    int nx, nc, mdep=dep[dot.rbegin()->x];
    for(int i=1; i<=mdep; i++) {
        nd[i]=nd[i-1];
        while(j<dot.size() && dep[dot[j].x]<=i) {
            nx=dot[j].x, nc=dot[j].k;
            auto it=s[nc].lower_bound(dl[nx]);
            int rx=(it==s[nc].end()?-1:dd[*it]);
            int lx=(it==s[nc].begin()?-1:dd[*(--it)]);
            updata(nd[i], 1, n, dl[nx], val[nc], i);
            if(rx!=-1 && lx!=-1)
                updata(nd[i], 1, n, dl[lca(lx, rx)], val[nc], i);
            if(lx!=-1)
                updata(nd[i], 1, n, dl[lca(lx, nx)], inv[val[nc]], i);
            if(rx!=-1)
                updata(nd[i], 1, n, dl[lca(nx, rx)], inv[val[nc]], i);
            s[nc].insert(dl[nx]);
            j++;
        }
    }
    
    /* query */
    int q, lstans=0;
    gn(q);
    while(q--) {
        gn(u), gn(v), u=u^(k*lstans), v=v^(k*lstans);
        printf("%d\n", lstans=query(nd[min(dep[u]+v, mdep)], 1, n, dl[u], dr[u]));
    }
    return 0;
}