[鍊分治 重鍊剖分 FWT] BZOJ 4911 [Sdoi2017]切樹遊戲

我鍊分治是從immortalCO今年論文學來的

就是一個序列上能夠維護的東西，把他搬到重鍊上，先處理好兒子重鍊的答案，然後把對這條重鍊上的影響累加在這條重鍊上

修改就爬重鍊一路改上去

然後就是套路 FWT一下就能加和乘了

注意0沒有逆元

複雜度 O(mnlog2n) 實際上樹鍊剖分是跑不滿的

rank1 開心 O(∩_∩)O~~

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#define pb push_back
using namespace std;

inline char nc(){
  static char buf[],*p1=buf,*p2=buf;
  return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){
  char c=nc(),b=;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-;
  for (x=;c>='0' && c<='9';x=x*+c-'0',c=nc()); x*=b;
}
inline void read(char &x){
  for (x=nc();x!='Q' && x!='C';x=nc());
}

const int N=;
const int KK=;

const int P=;
const int INV2=(P+)>>;

inline void FWT(int *a,int n,int r){
  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 (r) a[j+k]=(x+y)%P,a[j+k+i]=(x+P-y)%P;
    else a[j+k]=(x+y)*INV2%P,a[j+k+i]=(x+P-y)*INV2%P;
      }
}

int K,kx[KK][KK];
int inv[P];
inline void Pre(int n){
  for (int i=;i<n;i++)
    kx[i][i]=,FWT(kx[i],n,);
  inv[]=;
  for (int i=;i<P;i++)
    inv[i]=(P-P/i)*inv[P%i]%P;
}

struct edge{
  int u,v,next;
}G[N<<];
int head[N],inum;
#define V G[p].v
inline void add(int u,int v,int p){
  G[p].u=u; G[p].v=v; G[p].next=head[u]; head[u]=p;
}

int fat[N],top[N],size[N];
int depth[N];
inline void dfs(int u,int fa){
  fat[u]=fa; size[u]=; depth[u]=depth[fa]+;
  for (int p=head[u];p;p=G[p].next)
    if (V!=fa)
      dfs(V,u),size[u]+=size[V]; 
}
vector<int> p[N];
inline void find(int u,int fa,int z){
  top[u]=z; p[z].pb(u);
  int maxv=,son=;
  for (int p=head[u];p;p=G[p].next)
    if (V!=fa && size[V]>maxv)
      maxv=size[son=V];
  if (son) find(son,u,z);
  for (int p=head[u];p;p=G[p].next)
    if (V!=fa && V!=son)
      find(V,u,V);
}


const int M=;
int ncnt,rt[N],pos[N];
int ps[M],ls[M],rs[M];
int sum[M][KK],lval[M][KK],rval[M][KK],val[M][KK];

inline void upd(int x){
  int L=ls[x],R=rs[x];
  for (int i=;i<K;i++){
    val[x][i]=(val[L][i]+val[R][i]+rval[L][i]*lval[R][i])%P;
    lval[x][i]=(lval[L][i]+lval[R][i]*sum[L][i])%P;
    rval[x][i]=(rval[R][i]+rval[L][i]*sum[R][i])%P;
    sum[x][i]=sum[L][i]*sum[R][i]%P;
  }
}

struct abcd{
  int x,y;
  abcd(){ }
  abcd(int num){
    if (num) x=num,y=; else x=,y=;
  }
  abcd & operator *= (int a){
    if (a==) y++; else x=x*a%P;
    return *this;
  }
  abcd & operator /= (int a){
    if (a==) y--; else x=x*inv[a]%P;
    return *this;
  }
  int val(){
    return y?:x;
  }
};

abcd base[N][KK];

inline void Build(int &x,int l,int r,int t){
  x=++ncnt;
  if (l==r){
    for (int i=;i<K;i++)
      val[x][i]=lval[x][i]=rval[x][i]=sum[x][i]=base[p[t][l-]][i].val();
    pos[p[t][l-]]=x;
    return;
  }
  int mid=(l+r)>>;
  Build(ls[x],l,mid,t); Build(rs[x],mid+,r,t);
  upd(x); ps[ls[x]]=ps[rs[x]]=x;
}

int ans[KK],tmp[KK];

inline void Modify(int u){
  int t=top[u];
  if (fat[t])
    for (int j=;j<K;j++)
      base[fat[t]][j]/=(lval[rt[t]][j]+kx[][j])%P;
  for (int j=;j<K;j++)
    ans[j]=(ans[j]+P-val[rt[t]][j])%P;

  int x=pos[u];
  for (int i=;i<K;i++)
    val[x][i]=lval[x][i]=rval[x][i]=sum[x][i]=base[u][i].val();
  x=ps[x];
  while (x)
    upd(x),x=ps[x];

  if (fat[t])
    for (int j=;j<K;j++)
      base[fat[t]][j]*=(lval[rt[t]][j]+kx[][j])%P;
  for (int j=;j<K;j++)
    ans[j]=(ans[j]+val[rt[t]][j])%P;
}

int n,vv[N];

int lst[N],pnt;
inline bool cmp(int x,int y){
  return depth[x]>depth[y];
}

int main(){
  int x,y,Q; char order;
  freopen("t.in","r",stdin);
  freopen("t.out","w",stdout);
  read(n); read(K); int t=; while (t<K) t<<=; K=t;
  Pre(K);
  for (int i=;i<=n;i++){
    read(x); vv[i]=x;
    for (int j=;j<K;j++) base[i][j]=abcd(kx[x][j]);
  }
  for (int i=;i<n;i++)
    read(x),read(y),add(x,y,++inum),add(y,x,++inum);
  dfs(,); find(,,);
  for (int i=;i<=n;i++) if (top[i]==i) lst[++pnt]=i;
  sort(lst+,lst+pnt+,cmp);
  for (int i=;i<=pnt;i++){
    int x=lst[i];
    Build(rt[x],,p[x].size(),x);
    if (fat[x]){
      int f=fat[x];
      for (int j=;j<K;j++)
    base[f][j]*=(lval[rt[x]][j]+kx[][j])%P;
    }
    for (int j=;j<K;j++)
      ans[j]=(ans[j]+val[rt[x]][j])%P;
  }

  read(Q);
  while (Q--){
    read(order); read(x);
    if (order=='C'){
      read(y);
      for (int j=;j<K;j++)
    base[x][j]/=kx[vv[x]][j];
      vv[x]=y;
      for (int j=;j<K;j++)
    base[x][j]*=kx[vv[x]][j];
      while (x!=)
    Modify(x),x=fat[top[x]];
    }else if (order=='Q'){
      for (int j=;j<K;j++) tmp[j]=ans[j];
      FWT(tmp,K,);
      printf("%d\n",tmp[x]);
    }
  }
  return ;
}