Wannafly 练习赛7 C 随机树

#include <bits/stdc++.h>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
using namespace std;
const int maxn=1e5+5;
const int P=1e9+7;
typedef long long ll;
int n,u,v,q,dfs_clock,id[maxn],L[maxn],R[maxn],in[maxn],a[maxn];
int primes[]={2,3,5,7,11,13};
int ans[6];
ll sum[maxn<<2][6];
char s[10];
vector<int>G[maxn];
void dfs(int u,int f){
    L[u]=++dfs_clock;
    id[dfs_clock]=u;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==f) continue;
        dfs(v,u);
    }
    R[u]=dfs_clock;
}
void pushup(int root){
    for (int i=0;i<6;i++) sum[root][i]=sum[root<<1][i]+sum[root<<1|1][i];
}
void build(int root,int l,int r){
    if (l==r){
        int tmp=a[id[l]];
        for (int i=0;i<6;i++){
            int cnt=0;
            if (tmp%primes[i]==0){
                while (tmp%primes[i]==0){
                    tmp/=primes[i];
                    cnt++;
                }
            }
            sum[root][i]=cnt;
        }
        return;
    }
    int mid=l+((r-l)>>1);
    build(lson);
    build(rson);
    pushup(root);
}
void query(int root,int l,int r,int L,int R){
    if (L<=l && r<=R){
        for (int i=0;i<6;i++){
            ans[i]+=sum[root][i];
        }
        return;
    }
    int mid=l+((r-l)>>1);
    if (L<=mid) query(lson,L,R);
    if (mid<R) query(rson,L,R);
    pushup(root);
    return;
}
void update(int root,int l,int r,int u,int v){
    if (l==r){
        int tmp=v;
        for (int i=0;i<6;i++){
            int cnt=0;
            if (tmp%primes[i]==0){
                while (tmp%primes[i]==0){
                    tmp/=primes[i];
                    cnt++;
                }
            }
            sum[root][i]+=cnt;
        }
        return;
    }
    int mid=l+((r-l)>>1);
    if (u<=mid) update(lson,u,v);
    else update(rson,u,v);
    pushup(root);
}
int ksm(int a,int n){
    int res=1;
    while (n){
        if (n&1) res=(1LL*res*a)%P;
        a=(1LL*a*a)%P;
        n>>=1;
    }
    return res;
}
int main(){
    scanf("%d",&n);
    for (int i=2;i<=n;i++){
        scanf("%d%d",&u,&v);
        u++,v++;
        G[u].push_back(v);
        in[v]++;
    }
    int f;
    for (int i=1;i<=n;i++) if (in[i]==0){
        f=i;
        break;
    }
    dfs(f,-1);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);
    for (scanf("%d",&q);q--;){
        scanf("%s",s);
        if (s[0]=='R'){
            int u;scanf("%d",&u);
            u++;
            memset(ans,0,sizeof(ans));
            query(1,1,n,L[u],R[u]);
            int a=1,num=1;
            for (int i=0;i<6;i++){
                a=1LL*a*(ans[i]+1)%P;
                num=1LL*num*ksm(primes[i],ans[i])%P;
            }
            printf("%d %d\n",num,a);
        }
        else{
            int u,x;scanf("%d%d",&u,&x);
            u++;
            update(1,1,n,L[u],x);
        }
    }
    return 0;
}