P5499 [LnOI2019]Abbi并不想研学

· · 题解

\text{Foreword}

一道被洛谷遗忘的闹鬼题。
第一眼：ddp？看一眼通过人数：怕不是道神题吧...
开始使用大脑：...这暴力跳重链更新不就是 O(n\log n) 吗...
再看看通过人数...我一定是哪里假了...
再想想我的做法...哪里假了啊...写写试试？

提交...过了...
？？？
连题解都没有？？那我水一篇吧...

\text{Solution}

总所周知，树剖每个节点到根的重链个数严格不超过 \log n 的。
所以对于每个点维护其 charge_x 集合内所有点点权的乘积与加和，再对每个链头维护链上所有点点权的乘积与加和，修改的时候暴力维护即可。

\text{Code}

#include<bits/stdc++.h>
#include<string>
using namespace std;
#define ll long long
#define ull unsigned ll
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")

inline ll read() {
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}
  while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}
const int N=1e6+100;
const int mod=99991;

bool mem1;

inline ll ksm(ll x,ll k){
  ll res(1);
  while(k){
    if(k&1) res=res*x%mod;
    x=x*x%mod;
    k>>=1;
  }
  return res;
}

int n,m,k;

vector<int>e[N];
ll mul[N],sum[N],cur[N],ori[N];
ll top_mul[N],top_sum[N],ni[N];
int top[N],fa[N],siz[N],hson[N];
int a[N];
void dfs1(int x,int f){
  fa[x]=f;
  siz[x]=1;
  for(int to:e[x]){
    if(to==f) continue;
    dfs1(to,x);
    siz[x]+=siz[to];
    if(siz[to]>siz[hson[x]]||(siz[to]==siz[hson[x]]&&to<hson[x])) hson[x]=to;
  }
  return;
}
bool tag[N];
void dfs2(int x,int tp){
  top[x]=tp;
  mul[x]=1;
  if(x==top[x]) top_mul[x]=1;
  if(hson[x]) dfs2(hson[x],tp);
  for(int to:e[x]){
    if(to==hson[x]) continue;
    dfs2(to,to);
  }
  if(e[x].empty()) cur[x]=a[x],tag[x]=1;
  else cur[x]=a[x]?mul[x]:sum[x];
  if(!tag[x]) return;
  if(top[x]>1){
    mul[fa[top[x]]]=mul[fa[top[x]]]*cur[x]%mod;
    sum[fa[top[x]]]=(sum[fa[top[x]]]+cur[x])%mod;
    tag[fa[top[x]]]=1;
  }
  top_mul[top[x]]=top_mul[top[x]]*cur[x]%mod;
  top_sum[top[x]]=(top_sum[top[x]]+cur[x])%mod;
  //printf("x=%d cur=%lld\n",x,cur[x]);
  return;
}
inline void upd(int x){
  if(!tag[x]) return;
  ori[x]=cur[x];
  if(e[x].empty()) cur[x]=a[x];
  else cur[x]=a[x]?mul[x]:sum[x];
  top_mul[top[x]]=top_mul[top[x]]*ni[ori[x]]%mod;
  top_sum[top[x]]=(top_sum[top[x]]+mod-ori[x])%mod;
  top_mul[top[x]]=top_mul[top[x]]*cur[x]%mod;
  top_sum[top[x]]=(top_sum[top[x]]+cur[x])%mod;

  if(top[x]>1){
    mul[fa[top[x]]]=mul[fa[top[x]]]*ni[ori[x]]%mod;
    sum[fa[top[x]]]=(sum[fa[top[x]]]+mod-ori[x])%mod;
    mul[fa[top[x]]]=mul[fa[top[x]]]*cur[x]%mod;
    sum[fa[top[x]]]=(sum[fa[top[x]]]+cur[x])%mod;
    upd(fa[top[x]]);
  }
}

bool mem2;
signed main() {
#ifndef ONLINE_JUDGE
  freopen("a.in","r",stdin);
  freopen("a.out","w",stdout);
#endif
  for(int i=1;i<mod;i++) ni[i]=ksm(i,mod-2);
  n=read();m=read();
  for(int i=2;i<=n;i++) e[read()].push_back(i);
  for(int i=1;i<=n;i++) a[i]=read();
  dfs1(1,0);
  dfs2(1,1);
  for(int i=1;i<=m;i++){
    int op=read(),x=read();
    if(op==1){
      int w=read();
      a[x]=w;
      upd(x);
    }
    else if(op==2){
      a[x]^=1;
      upd(x);
    }
    else printf("%lld %lld\n",top_sum[top[x]],top_mul[top[x]]);
  }
  return 0;
}
/*
  3 1
  2 3 3 1
  1 1
*/