题解：P5499 [LnOI2019] Abbi 并不想研学

· · 题解

按照题意模拟即可。这甚至都告诉你了怎么树链剖分，虽然有点难调，但真的不是绿题吗。

维护每条长链所有数的和与乘积，切换符号的时候可以快速获取这条链的和/乘积，之后再向上修改，注意到每次修改一个叶子节点只有可能影响到链头，向上跳链，动态维护即可。注意撤销的顺序，这里很容易写错。同时这里因为有乘法取模所以需要预处理逆元。

:::success[AC Code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5,mod=99991;
struct Edge{
    int to,nxt;
}e[N];
int head[N],tot;
void add_edge(int u,int v)
{
    tot++;
    e[tot].to=v;
    e[tot].nxt=head[u];
    head[u]=tot;
}
int inv[N];
int n,m,a[N],sum[N],mul[N],sv[N],mv[N];
//sum and mul are top
//sv and mv are light son
int fa[N],son[N],siz[N],top[N],only[N];
int qpow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void dfs1(int u)
{
    siz[u]=1;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        dfs1(v);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]||(siz[v]==siz[son[u]]&&v<son[u]))
            son[u]=v;
        only[u]++;
    }
    if(only[u]!=1)only[u]=0;
}
void dfs2(int u,int tp)
{
    mul[u]=mv[u]=1;
    top[u]=tp;
    if(son[u]){
        dfs2(son[u],tp);
        only[u]=1;
    }
    else sv[u]=mv[u]=a[u];
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==son[u])continue;
        dfs2(v,v);
        only[u]=0;
        mv[u]=mv[u]*mul[v]%mod;
        sv[u]=(sv[u]+sum[v])%mod;
    }
    if(only[u])return;
    int w=a[u]?mv[u]:sv[u];
    mul[top[u]]=mul[top[u]]*w%mod;
    sum[top[u]]=(sum[top[u]]+w)%mod;
}
void pushup(int u,int os,int om)
{
    while(u)
    {
        int v=top[u];
        u=fa[top[u]];
        int w=a[u]?mv[u]:sv[u];
        sv[u]=(sv[u]-os+mod)%mod;
        mv[u]=mv[u]*inv[om]%mod;
        sv[u]=(sv[u]+sum[v])%mod;
        mv[u]=mv[u]*mul[v]%mod;
        os=sum[top[u]];
        om=mul[top[u]];
        mul[top[u]]=(mul[top[u]]*inv[w])%mod;
        sum[top[u]]=(sum[top[u]]-w+mod)%mod;
        w=a[u]?mv[u]:sv[u];
        mul[top[u]]=mul[top[u]]*w%mod;
        sum[top[u]]=(sum[top[u]]+w)%mod;
    }
}
void update1(int u,int k)
{
    int os=sum[top[u]],om=mul[top[u]];
    mul[top[u]]=mul[top[u]]*inv[a[u]]%mod;
    sum[top[u]]=(sum[top[u]]-a[u]+mod)%mod;
    sv[u]=mv[u]=a[u]=k;
    mul[top[u]]=mul[top[u]]*k%mod;
    sum[top[u]]=(sum[top[u]]+k)%mod;
    pushup(u,os,om);
}
void update2(int u)
{
    if(only[u])return;
    int os=sum[top[u]],om=mul[top[u]];
    int wo=mv[u],wn=sv[u];
    if(!a[u])swap(wo,wn);
    mul[top[u]]=mul[top[u]]*inv[wo]%mod;
    mul[top[u]]=mul[top[u]]*wn%mod;
    sum[top[u]]=(sum[top[u]]-wo+mod)%mod;
    sum[top[u]]=(sum[top[u]]+wn)%mod;
    a[u]^=1;
    pushup(u,os,om);
}
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    for(int i=1;i<mod;i++)
        inv[i]=qpow(i,mod-2);
    cin>>n>>m;
    for(int i=2;i<=n;i++)
    {
        cin>>fa[i];
        add_edge(fa[i],i);
    }
    dfs1(1);
    for(int i=1;i<=n;i++)
        cin>>a[i];
    dfs2(1,1);
    while(m--)
    {
        int c,k,val;
        cin>>c>>k;
        if(c==1)
        {
            cin>>val;
            update1(k,val);
        }
        if(c==2)
            update2(k);
        if(c==3)
            cout<<sum[top[k]]<<' '<<mul[top[k]]<<'\n';
    }
    return 0;
}

:::