https://loj.ac/problem/2130

题目描述

  软件的关系形成一棵树，安装某软件前必须安装它依赖的软件，卸载某软件时必须卸载被它依赖的软件，求卸载或安装某软件会影响多少软件的状态。

思路

  我们考虑对于安装某个软件，我们只要求它的子树中未被下载的软件数即为答案。而对于一次卸载，我们需要求出这个点到根节点的路径中有多少节点已被安装。所以我们可以用树链剖分，安装时直接按线段树的区间修改即可，而路径的操作就把\(x\)不断按重链往上跳，修改路径即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;

int nxt[N<<1],to[N<<1],tot,head[N];
void add_edge(int x,int y)
{
    nxt[++tot]=head[x];
    head[x]=tot;
    to[tot]=y;
}

int siz[N],fa[N],dep[N],son[N],top[N];
int seg[N<<2],sum[N<<2],rev[N<<2],lazy[N<<2];
int ans;
void dfs1(int u,int father)
{
    siz[u]=1;fa[u]=father;
    dep[u]=dep[father]+1;
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(v==father)continue ;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
void dfs2(int u,int father)
{
    if(son[u])
    {
        seg[son[u]]=++seg[0];
        rev[seg[0]]=son[u];
        top[son[u]]=top[u];
        dfs2(son[u],u);
    }
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(top[v])continue ;
        seg[v]=++seg[0];
        rev[seg[0]]=v;
        top[v]=v;
        dfs2(v,u);
    }
}
void pushup(int k)
{
    sum[k]=sum[k<<1]+sum[k<<1|1];
}
void build(int k,int l,int r)
{
    lazy[k]=-1;
    if(l==r)
    {
        sum[k]=1;
        return ;
    }
    int mid=l+r>>1;
    build(k<<1,l,mid);build(k<<1|1,mid+1,r);
    pushup(k);
}
void add(int k,int l,int r,int v)
{
    sum[k]=(r-l+1)*v;
    lazy[k]=v;
}
void pushdown(int k,int l,int r,int mid)
{
    if(lazy[k]==-1)return ;
    add(k<<1,l,mid,lazy[k]);
    add(k<<1|1,mid+1,r,lazy[k]);
    lazy[k]=-1;
}
void change(int k,int l,int r,int x,int y,int val)
{
    if(r<x||l>y)return ;
    if(l>=x&&r<=y)
    {
        sum[k]=(r-l+1)*val;
        lazy[k]=val;
        return ;
    }
    int mid=l+r>>1;
    pushdown(k,l,r,mid);
    if(x<=mid)change(k<<1,l,mid,x,y,val);
    if(y>mid)change(k<<1|1,mid+1,r,x,y,val);
    pushup(k);
}
void query(int k,int l,int r,int x,int y)
{
    if(r<x||l>y)return;
    if(l>=x&&r<=y)
    {
        ans+=sum[k];
        return ;
    }
    int mid=l+r>>1;
    pushdown(k,l,r,mid);
    if(x<=mid)query(k<<1,l,mid,x,y);
    if(y>mid)query(k<<1|1,mid+1,r,x,y);
}
void ask(int x,int y)
{
    int fx=top[x],fy=top[y];
    while(fx!=fy)
    {
        if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
        query(1,1,seg[0],seg[fx],seg[x]);
        x=fa[fx];fx=top[x];
    }
    if(dep[x]>dep[y])swap(x,y);
    query(1,1,seg[0],seg[x],seg[y]);
}
void find(int x,int y)
{
    int fx=top[x],fy=top[y];
    while(fx!=fy)
    {
        if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
        change(1,1,seg[0],seg[fx],seg[x],0);
        x=fa[fx];fx=top[x];
    }
    if(dep[x]>dep[y])swap(x,y);
    change(1,1,seg[0],seg[x],seg[y],0);
}

int read()
{
    int res=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();}
    return res*w;
}
void write(int x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
void writeln(int x)
{
    write(x);
    putchar('\n');
}

int main() 
{
    int n=read();
    for(int i=2;i<=n;i++)
    {
        int x=read()+1;
        add_edge(x,i);add_edge(i,x);
    }
    dfs1(1,0);
    seg[0]=seg[1]=rev[1]=top[1]=1;
    dfs2(1,0);
    build(1,1,seg[0]);
    int q=read();
    while(q--)
    {
        char s[10];
        scanf(" %s",s);
        int x=read()+1;
        if(s[0]=='i')
        {
            ans=0;
            ask(1,x);
            writeln(ans);
            find(1,x);
        }
        else
        {
            ans=0;
            query(1,1,seg[0],seg[x],seg[x]+siz[x]-1);
            writeln(siz[x]-ans);
            change(1,1,seg[0],seg[x],seg[x]+siz[x]-1,1);
        }
/*      for(int i=1;i<=n;i++)
        {
            ans=0;
            query(1,1,seg[0],seg[i],seg[i]);
            printf("%d %d\n",i,ans);
        }*/
    }
    return 0;
}