P2146 题解

__vector__ · 2022-06-14 21:57:46 · 个人记录

思路

对于 a 依赖 b 这种，就连一条 a 与 b 的边，可以发现最后会形成一颗以 0 为根的树。

• 对于安装软件 x，显然 0 \rightarrow x 路径上所有的软件都要安装，也就是将 0 \rightarrow x 路径上所有点的权值变为 1
• 对于删除软件 x，就是将以 x 为根的子树内的所有节点变为0

树链剖分即可。

代码

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    const int maxn=100005;
    int n,q;
    int head[maxn];
    struct EDGE
    {
        int to,nxt;
    }edge[maxn<<1];
    int cnt;
    inline void add(int u,int to)
    {
        edge[++cnt].to=to;
        edge[cnt].nxt=head[u];
        head[u]=cnt;
    } 
    int size[maxn<<3];
    int dfn[maxn<<3];
    int rank[maxn<<3];
    int hs[maxn<<3];
    int fa[maxn<<3];
    int nodecnt;
    int top[maxn<<3];
    int dep[maxn<<3];
    void dfs1(int u,int _fa)
    {
        dep[u]=dep[_fa]+1;
        size[u]=1;
        fa[u]=_fa;
        int imax=0;
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int to=edge[i].to;
            if(to==_fa)continue;
            dfs1(to,u);
            size[u]+=size[to];
            if(size[to]>=imax)
            {
                imax=size[to];
                hs[u]=to;
            }
        }
    }
    void dfs2(int u,int _top)
    {
        dfn[u]=++nodecnt;
        rank[nodecnt]=u;
        top[u]=_top;
        if(hs[u])
        {
            dfs2(hs[u],_top);
        }
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int to=edge[i].to;
            if(to==fa[u]||to==hs[u])continue;
            dfs2(to,to);
        }
    }
    int val[maxn<<3],lazy[maxn<<3];
    int L[maxn<<3],R[maxn<<3];
    void build(int pos,int l,int r)
    {
        L[pos]=l;
        R[pos]=r;
        lazy[pos]=-1;
        if(l==r)
        {
            return;
        }
        int mid=(l+r)>>1;
        build(pos<<1,l,mid);
        build(pos<<1|1,mid+1,r);
    }
    inline int get_len(int i)
    {
        return (R[i]-L[i]+1);
    }
    inline void push_down(int i)
    {
        if(lazy[i]==-1)return;
        lazy[i<<1]=lazy[i];
        lazy[i<<1|1]=lazy[i];
        val[i<<1]=lazy[i]*get_len(i<<1);
        val[i<<1|1]=lazy[i]*get_len(i<<1|1);
        lazy[i]=-1;
    }
    inline void push_up(int i)
    {
        val[i]=val[i<<1]+val[i<<1|1];
    }
    void modify(int pos,int _l,int _r,int l,int r,int _val)
    {
        if(_l>=l&&_r<=r)
        {
            lazy[pos]=_val;
            val[pos]=(_val)*get_len(pos);
            return;
        }
        if(_r<l||_l>r)return;
        push_down(pos);
        int mid=(_l+_r)>>1;
        if(mid>=l)modify(pos<<1,_l,mid,l,r,_val);
        if(mid<r)modify(pos<<1|1,mid+1,_r,l,r,_val);
        push_up(pos);
    }
    void Modify(int x,int y,int _val)
    {
        while(top[x]!=top[y])
        {
            if(dep[top[x]]<dep[top[y]])swap(x,y);
            modify(1,1,n,dfn[top[x]],dfn[x],_val);
            x=fa[top[x]];
        }
        if(dep[x]>dep[y])swap(x,y);
        modify(1,1,n,dfn[x],dfn[y],_val);
    }
    void main()
    {
        scanf("%d",&n);
        for(int i=1;i<n;i++)
        {
            int b;
            scanf("%d",&b);
            add(i,b);
            add(b,i);
        }
        dfs1(0,n*6);
        dfs2(0,0);
        build(1,1,n);
        //-------------------
        char op[10];
        int x;
        scanf("%d",&q);
        for(int i=1;i<=q;i++)
        {
            scanf("%s%d",op,&x);
            if(op[0]=='i')
            {
                int ai=val[1];
                Modify(0,x,1);
                int bi=val[1];
                printf("%d\n",abs(ai-bi));
            }
            if(op[0]=='u')
            {
                int ai=val[1];
                modify(1,1,n,dfn[x],dfn[x]+size[x]-1,0);
                int bi=val[1];
                printf("%d\n",abs(ai-bi));
            }
        }       
    }
}
int main()
{
    Main::main();
    return 0;
}