题目链接：
http://172.16.0.132/senior/#contest/show/2538/2
题目：
小S决定从某一个节点$u$开始对其子树中与$u$距离小于$K$的节点代表的花树进行采摘。
特别的，节点$u$代表的花树也会被采摘。依旧受限于精力，小S并不会亲自去采摘而是使用Extremely Strong的工具进行采摘。
我们定义一个工具的能力为$c$，小S会采摘的山树集合为$T$。那么小S能采摘到的山花数量$f_T = \prod _{i∈T} (a_i, c)$
现在对于给定的树和阀值$K$，小S想要知道每一组询问的$f_T$
题解：
考虑按质因数分类计算每个点的贡献
对于一个质因子，我们把询问$c$值和点权$a$值放在一起按照指数排序。
先从前往后扫，显然对于一个询问当前贡献为之前的点权指数之和；再从后往前扫，对于一个询问当前的贡献是后面的点的个数乘上当前询问的指数。这就是经典的通过排序确定大小关系后计算贡献的栗子
直接用树状数组在$dfs$序上维护即可
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll; const int N=1e5+;
const int mo=;
const int M=1e7+;
int n,Q,k,tot,tim,cnt,tp;
int t[N],dfn[N],pri[N],fk[N],ed[N],vis[M],head[N],fa[N],st[N];
ll ANS[N];
struct EDGE{
int to,nxt;
}edge[N<<];
struct QUE{
int x,c;
}q[N];
struct node{
int k,ty,id;
}ck[N<<];
bool operator < (node x,node y) {return x.k<y.k||(x.k==y.k&&x.ty<y.ty);}
vector <node> pi[N];
inline int read(){
char ch=getchar();int s=,f=;
while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}
return s*f;
}
void div(int x,int ty,int id)
{
for (int i=;i*i<=x;i++)
{
if (x%i) continue;
int s=;
while (x%i==) x/=i,++s;
if (!vis[i]) pri[++cnt]=i,vis[i]=cnt;
pi[vis[i]].push_back((node){s,ty,id});
}
if (x>)
{
if (!vis[x]) pri[++cnt]=x,vis[x]=cnt;
pi[vis[x]].push_back((node){,ty,id});
}
}
void link(int u,int v){edge[++tot]=(EDGE){v,head[u]};head[u]=tot;}
void dfs(int x,int pre)
{
dfn[x]=++tim;st[++tp]=x;
if (tp>k) fk[x]=st[tp-k];
for (int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;
if (y==pre) continue;
dfs(y,x);
}
tp--;ed[x]=tim;
}
void modify(int x,int y)
{
if (!x) return;
while (x<=n)
{
t[x]+=y;
x+=x&-x;
}
}
int query(int x)
{
int re=;
while (x)
{
re+=t[x];
x-=x&-x;
}
return re;
}
ll qpow(ll a,ll b)
{
ll re=;
for (;b;b>>=,a=a*a%mo) if (b&) re=re*a%mo;
return re;
}
int main()
{
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
n=read();Q=read();k=read();
for (int i=,a;i<=n;i++) a=read(),div(a,,i);
for (int i=,u,v;i<n;i++)
{
u=read();v=read();
link(u,v);link(v,u);
}
dfs(,);
for (int i=;i<=Q;i++)
{
q[i].x=read();q[i].c=read();
div(q[i].c,,i);
ANS[i]=;
}
for (int j=;j<=cnt;j++)
{
int pnt=pi[j].size();
sort(pi[j].begin(),pi[j].end());
memset(t,,sizeof(t));
for (int i=;i<pnt;i++)
{
int id=pi[j][i].id;
if (pi[j][i].ty==)
{
modify(dfn[fk[id]],-pi[j][i].k);
modify(dfn[id],pi[j][i].k);
}
else
{
int p=query(ed[q[id].x])-query(dfn[q[id].x]-);
(ANS[id]*=qpow(pri[j],p))%=mo;
}
}
for (int i=;i<pnt;i++)
{
int id=pi[j][i].id;
if (pi[j][i].ty==)
{
modify(dfn[fk[id]],pi[j][i].k);
modify(dfn[id],-pi[j][i].k);
}
}
for (int i=pnt-;i>=;i--)
{
int id=pi[j][i].id;
if (pi[j][i].ty==)
{
modify(dfn[fk[id]],-);
modify(dfn[id],);
}
else
{
int p=query(ed[q[id].x])-query(dfn[q[id].x]-);
(ANS[id]*=qpow(pri[j],p*pi[j][i].k))%=mo;
}
}
for (int i=pnt-;i>=;i--)
{
int id=pi[j][i].id;
if (pi[j][i].ty==)
{
modify(dfn[fk[id]],);
modify(dfn[id],-);
}
}
}
for (int i=;i<=Q;i++) printf("%lld\n",ANS[i]);
return ;
}