![[Noi2015]软件包管理器 题解 [Noi2015]软件包管理器 题解](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700)
题目大意:
有n个软件安装包,除第一个以外,其他的要在另一个安装包的基础上安装,且无环,问在安装和卸载某个软件包时,这个操作实际上会改变多少个软件包的安装状态。
思路:
可构成树,用树链剖分,线段树。已安装的为1,未安装的为0。对于安装操作,就是询问x到0的路径上0的个数,然后把这个路径赋为1;对于卸载操作,就是询问x的子树中1的个数,然后把子树赋为0。
代码:
#include<cstdio>
#include<iostream>
#define M 800500
using namespace std; int n,cnt,dfn,hson[M],pa[M],id[M],to[M],top[M],vis[M],last[M],next[M],head[M],deep[M],size[M],sum[M],sz[M],lazy[M]; void ins(int x,int y)
{
to[++cnt]=y,next[cnt]=head[x],head[x]=cnt;
} void dfs1(int x)
{
size[x]=;
for (int i=head[x];i;i=next[i])
if (to[i]!=pa[x])
{
pa[to[i]]=x,deep[to[i]]=deep[x]+;
dfs1(to[i]),size[x]+=size[to[i]];
if (size[to[i]]>size[hson[x]]) hson[x]=to[i];
}
} void dfs2(int x,int tp)
{
id[x]=++dfn,top[x]=tp;
if (hson[x]) dfs2(hson[x],tp);
for (int i=head[x];i;i=next[i])
if (to[i]!=pa[x]&&to[i]!=hson[x]) dfs2(to[i],to[i]);
last[x]=dfn;
} void build(int l,int r,int cur)
{
if (l==r) { sum[cur]=,lazy[cur]=-,sz[cur]=; return; }
int mid=l+r>>;
build(l,mid,cur<<),build(mid+,r,cur<<|);
sz[cur]=sz[cur<<]+sz[cur<<|];
} void push_down(int k)
{
if (lazy[k]!=-)
{
sum[k<<]=sz[k<<]*lazy[k],sum[k<<|]=sz[k<<|]*lazy[k];
lazy[k<<]=lazy[k<<|]=lazy[k],lazy[k]=-;
}
} void change(int L,int R,int l,int r,int cur,int val)
{
if (L==l && R==r) { sum[cur]=val*sz[cur]; lazy[cur]=val; return; }
int mid=L+R>>; push_down(cur);
if (r<=mid) change(L,mid,l,r,cur<<,val);
else if (l>mid) change(mid+,R,l,r,cur<<|,val);
else change(L,mid,l,mid,cur<<,val),change(mid+,R,mid+,r,cur<<|,val);
sum[cur]=sum[cur<<]+sum[cur<<|];
} int ask(int L,int R,int l,int r,int cur)
{
if (L==l && R==r) return sum[cur];
int mid=L+R>>; push_down(cur);
if (r<=mid) return ask(L,mid,l,r,cur<<);
else if (l>mid) return ask(mid+,R,l,r,cur<<|);
else return ask(L,mid,l,mid,cur<<)+ask(mid+,R,mid+,r,cur<<|);
} void add(int x,int y)
{
if (deep[x]<deep[y]) swap(x,y);
int sum=,t=deep[x]-deep[y]+;
for (;top[x]!=top[y];x=pa[top[x]])
{
if (deep[top[x]]<deep[top[y]]) swap(x,y);
sum+=ask(,n,id[top[x]],id[x],);
change(,n,id[top[x]],id[x],,);
}
if (deep[x]>deep[y]) swap(x,y);
sum+=ask(,n,id[x],id[y],);
change(,n,id[x],id[y],,);
printf("%d\n",t-sum);
} int main()
{
int i,m,x;
scanf("%d",&n);
for (i=;i<n;i++) scanf("%d",&m),ins(m+,i+);
scanf("%d",&m),dfs1(),dfs2(,),build(,n,);
for (i=;i<=m;i++)
{
char ch[];
scanf("%s%d",ch,&x),x++;
if (ch[]=='i') add(,x);
else printf("%d\n",ask(,n,id[x],last[x],)),change(,n,id[x],last[x],,);
}
return ;
}