UOJ #128 [NOI2015 D1T2] 软件包管理器

Linux 用户和 OS X 用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。Debian/Ubuntu 使用的 apt-get，Fedora/CentOS 使用的 yum，以及 OS X 下可用的 homebrew 都是优秀的软件包管理器。

你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。如果软件包  A A 依赖软件包  B B，那么安装软件包  A A 以前，必须先安装软件包  B B。同时，如果想要卸载软件包  B B，则必须卸载软件包  A A。现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除  0 0 号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而  0 0 号软件包不依赖任何一个软件包。依赖关系不存在环（若有  m m  (m≥2) (m≥2) 个软件包  A1,A2,A3,…,Am A1,A2,A3,…,Am，其中  A1 A1 依赖  A2 A2， A2 A2 依赖  A3 A3， A3 A3 依赖  A4 A4，……， Am?1 Am?1 依赖  Am Am，而  Am Am 依赖  A1 A1，则称这  m m 个软件包的依赖关系构成环），当然也不会有一个软件包依赖自己。

现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为  0 0。

输入格式

输入文件的第  1 1 行包含  1 1 个正整数  n n，表示软件包的总数。软件包从  0 0 开始编号。

随后一行包含  n?1 n?1 个整数，相邻整数之间用单个空格隔开，分别表示  1,2,3,…,n?2,n?1 1,2,3,…,n?2,n?1 号软件包依赖的软件包的编号。

接下来一行包含  1 1 个正整数  q q，表示询问的总数。

之后  q q 行，每行  1 1 个询问。询问分为两种：

• install  x x：表示安装软件包  x x
• uninstall  x x：表示卸载软件包  x x

你需要维护每个软件包的安装状态，一开始所有的软件包都处于未安装状态。对于每个操作，你需要输出这步操作会改变多少个软件包的安装状态，随后应用这个操作（即改变你维护的安装状态）。

输出格式

输出文件包括  q q 行。

输出文件的第  i i 行输出  1 1 个整数，为第  i i 步操作中改变安装状态的软件包数。

样例一

input

7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0

output

3
1
3
2
3

explanation

一开始所有的软件包都处于未安装状态。

安装  5 5 号软件包，需要安装  0,1,5 0,1,5 三个软件包。

之后安装  6 6 号软件包，只需要安装  6 6 号软件包。此时安装了  0,1,5,6 0,1,5,6 四个软件包。

卸载  1 1 号软件包需要卸载  1,5,6 1,5,6 三个软件包。此时只有  0 0 号软件包还处于安装状态。

之后安装  4 4 号软件包，需要安装  1,4 1,4 两个软件包。此时  0,1,4 0,1,4 处在安装状态。

最后，卸载  0 0 号软件包会卸载所有的软件包。

样例二

input

10
0 1 2 1 3 0 0 3 2
10
install 0
install 3
uninstall 2
install 7
install 5
install 9
uninstall 9
install 4
install 1
install 9

output

1
3
2
1
3
1
1
1
0
1

样例三

见样例数据下载。

限制与约定

时间限制： 1s 1s

空间限制： 512MB 512MB

下载

样例数据下载

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

树链剖分+线段树~

我可能是假树链剖分的受害者……第一次知道还能更新子树……

先求出答案，再更新树的标记即可。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;const int N=100005;int n,m,x,fi[N],w[N],ne[N],fa[N],id[N],dep[N],siz[N],son[N],top[N],cnt,r[N];
char s[20];struct node{int l,r,a,b;
}c[N<<2];int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;
}void add(int u,int v)
{w[++cnt]=v;ne[cnt]=fi[u];fi[u]=cnt;fa[v]=u;
}void dfs(int u)
{siz[u]=1;for(int i=fi[u];i;i=ne[i]){dep[w[i]]=dep[u]+1;dfs(w[i]);siz[u]+=siz[w[i]];if(siz[son[u]]<siz[w[i]]) son[u]=w[i];}
}void dfs1(int u,int la)
{id[u]=++cnt;top[u]=la;if(son[u]){dfs1(son[u],la);for(int i=fi[u];i;i=ne[i])if(w[i]!=son[u]) dfs1(w[i],w[i]);}r[u]=cnt;
}void build(int l,int r,int k)
{c[k].l=l;c[k].r=r;c[k].b=-1;if(l==r) return;int mid=l+r>>1;build(l,mid,k<<1);build(mid+1,r,k<<1|1);
}void update(int u,int v)
{c[u].a=v*(c[u].r-c[u].l+1);c[u].b=v;
}void pushdown(int u)
{if(c[u].b==-1) return;update(u<<1,c[u].b);update(u<<1|1,c[u].b);c[u].b=-1;
}int cal(int k,int u,int v)
{int l=c[k].l,r=c[k].r,mid=l+r>>1,now=0;if(l>=u && r<=v) return c[k].a;pushdown(k);if(u<=mid) now+=cal(k<<1,u,v);if(v>mid) now+=cal(k<<1|1,u,v);return now;
}void chan(int k,int u,int v,int kkz)
{int l=c[k].l,r=c[k].r,mid=l+r>>1;if(l>=u && r<=v){update(k,kkz);return;}pushdown(k);if(u<=mid) chan(k<<1,u,v,kkz);if(v>mid) chan(k<<1|1,u,v,kkz);c[k].a=c[k<<1].a+c[k<<1|1].a; 
}int cal_add(int u)
{int now=0;while(top[u]!=1){now+=cal(1,id[top[u]],id[u]);u=fa[top[u]];}return now+cal(1,1,id[u]);
}int sol_chan(int u)
{int v=1,now=0;while(top[u]!=1){chan(1,id[top[u]],id[u],1);u=fa[top[u]];}chan(1,1,id[u],1);
}int main()
{n=read();for(int i=2;i<=n;i++) x=read()+1,add(x,i);dep[1]=1;cnt=0;dfs(1);dfs1(1,1);build(1,n,1);m=read();while(m--){scanf("%s",s);x=read()+1;if(s[0]=='i'){printf("%d\n",dep[x]-cal_add(x));sol_chan(x);}else{printf("%d\n",cal(1,id[x],r[x]));chan(1,id[x],r[x],0);}}return 0;
}