[ DP FWT 鍊分治 ] [ SDOI2017 ] BZOJ4911 切樹遊戲

題解

#include<bits/stdc++.h>
using namespace std;
char nc() {
    static char buf[],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;
}
void Read(int& x) {
    char c=nc();
    for(;c<'0'||c>'9';c=nc());
    for(x=;c>='0'&&c<='9';x=(x<<)+(x<<)+c-,c=nc());
}
void Read(char& c) {
    char C=nc();
    for(;C!='C'&&C!='Q';) C=nc();
    c=C;
}
const int N=;
const int M=;
const int P=;
int inv[P];
struct Int {
    int a,b;
    Int(int a=,int b=):a(a),b(b){}
    void Set(int x) {
        if(x) a=x,b=;else a=,b=;
    }
    void operator /= (int x) {
        if(x) a=a*inv[(x+P)%P]%P;else --b;
    }
    void operator *= (int x) {
        if(x) a=a*x%P;else ++b;
    }
    int Get() {
        return b?:a;
    }
} g[N][M];
int k,n,m,x,y,q;
int h[N],t[N<<],nx[N<<],num;
int sz[N],f[N],d[N],top[N],son[N],sum[N],w[N];
int Rt[N],ls[N<<],rs[N<<],tot;
int c[N<<][M],cl[N<<][M],cr[N<<][M],ca[N<<][M];
int tmp[M][M];
int a[N],st[N];
int Ans[M];
char C;
void FWT(int* a,int n,int d) {
    for(int i=;i<n;i<<=)
        for(int j=;j<n;j+=i<<)
            for(int k=;k<i;k++) {
                int x=a[j+k],y=a[j+k+i];
                if(d) a[j+k]=(x+y)%P,a[j+k+i]=(x-y)%P;else a[j+k]=(x+y)*inv[]%P,a[j+k+i]=(x-y)*inv[]%P;
            }
}
void Add(int x,int y) {
    t[++num]=y;nx[num]=h[x];h[x]=num;
}
void Dfs(int x,int y) {
    f[x]=y;d[x]=d[y]+;sz[x]=;
    for(int i=h[x];i;i=nx[i])
        if(t[i]!=y) {
            Dfs(t[i],x);
            sz[x]+=sz[t[i]];
            if(sz[t[i]]>sz[son[x]]) son[x]=t[i];
        }
}
void Up(int x) {
    for(int i=;i<M;i++) {
        c[x][i]=(c[ls[x]][i]+c[rs[x]][i]+cr[ls[x]][i]*cl[rs[x]][i])%P;
        cl[x][i]=(cl[ls[x]][i]+ca[ls[x]][i]*cl[rs[x]][i])%P;
        cr[x][i]=(cr[rs[x]][i]+ca[rs[x]][i]*cr[ls[x]][i])%P;
        ca[x][i]=ca[ls[x]][i]*ca[rs[x]][i]%P;
    }
}
void Build(int& x,int l,int r) {
    x=++tot;
    if(l==r) {
        w[st[l]]=l;
        for(int i=;i<M;i++) c[x][i]=cl[x][i]=cr[x][i]=ca[x][i]=g[st[l]][i].Get();
        return;
    }
    int Mid=l+r>>;
    Build(ls[x],l,Mid);Build(rs[x],Mid+,r);
    Up(x);
}
void Update(int x,int l,int r,int y,int z) {
    if(l==r) {
        for(int i=;i<M;i++) c[x][i]=cl[x][i]=cr[x][i]=ca[x][i]=g[z][i].Get();
        return;
    }
    int Mid=l+r>>;
    if(y<=Mid) Update(ls[x],l,Mid,y,z);else Update(rs[x],Mid+,r,y,z);
    Up(x);
}
void Dfs1(int x,int y) {
    top[x]=y;
    for(int i=;i<M;i++) g[x][i].Set(tmp[a[x]][i]);
    if(son[x]) Dfs1(son[x],y);
    for(int i=h[x];i;i=nx[i])
        if(t[i]!=f[x]&&t[i]!=son[x]) {
            Dfs1(t[i],t[i]);
            for(int j=;j<M;j++) g[x][j]*=(cl[Rt[t[i]]][j]+tmp[][j])%P;
        }
    if(x==y) {
        int cnt=;
        for(int i=x;i;i=son[i]) st[++cnt]=i;
        Build(Rt[x],,cnt);sum[x]=cnt;
        for(int i=;i<M;i++) Ans[i]=(Ans[i]+c[Rt[x]][i])%P;
    }
}
void Modify(int x,int y) {
    if(a[x]==y) return;
    for(int i=;i<M;i++) g[x][i]/=tmp[a[x]][i],g[x][i]*=tmp[y][i];
    a[x]=y;
    while(top[x]!=) {
        int t=top[x];
        for(int i=;i<M;i++) g[f[t]][i]/=(cl[Rt[t]][i]+tmp[][i])%P,Ans[i]=(Ans[i]-c[Rt[t]][i])%P;
        Update(Rt[t],,sum[t],w[x],x);
        for(int i=;i<M;i++) g[f[t]][i]*=(cl[Rt[t]][i]+tmp[][i])%P,Ans[i]=(Ans[i]+c[Rt[t]][i])%P;
        x=f[t];
    }
    for(int i=;i<M;i++) Ans[i]=(Ans[i]-c[Rt[]][i])%P;
    Update(Rt[],,sum[],w[x],x);
    for(int i=;i<M;i++) Ans[i]=(Ans[i]+c[Rt[]][i])%P;
}
int main() {
    Read(n);Read(m);
    inv[]=inv[]=;
    for(int i=;i<P;i++) inv[i]=inv[P%i]*(P-P/i)%P;
    for(int i=;i<=n;i++) Read(a[i]);
    for(int i=;i<n;i++) Read(x),Read(y),Add(x,y),Add(y,x);
    for(int i=;i<M;i++) tmp[i][i]=,FWT(tmp[i],M,);
    Dfs(,);Dfs1(,);
    Read(q);
    while(q--) {
        Read(C);
        if(C=='C') Read(x),Read(y),Modify(x,y);else {
            Read(x);
            FWT(Ans,M,);
            printf("%d\n",(Ans[x]+P)%P);
            FWT(Ans,M,);
        }
    }
    return ;
}