[Luogu 2146] NOI2015 软件包管理器
树剖好题。
通过对题目的分析发现，这些软件构成一棵树，\(0\) 是树根。
每下载一个软件，需要下载根到这个软件的路径上的所有软件；
每卸载一个软件，需要删除这个软件构成的子树上的所有软件。
因此我们可以 HLD，然后用「0/1 线段树」来维护。
最初每一个点的点权都是 \(0\)。
下载 \(x\)：根到 \(x\) 的路径上，所有点权改为 \(1\)。
卸载 \(x\)：\(x\) 构成的子树上，所有点权改为 \(0\)。
每次操作前后线段树树根的值（即整棵树的和）的绝对值，就是这一次更新的软件数。
为了方便我直接把 \(0 \sim n-1\) 改成 \(1 \sim n\) 去做啦。
就这样，代码如下。
#include <cstdio>
#include <cstring>
const int MAXN=100010,MAXM=200010;
int n,q;
class HLD
{
public:
HLD(int num=0,int cnt=0):num(num),cnt(cnt)
{
memset(vis,0,sizeof vis);
memset(head,0,sizeof head);
}
void Init(void)
{
for(int i=2,x;i<=n;++i)
{
scanf("%d",&x);
AddEdges(i,x+1);
}
DFS1(1,1),DFS2(1,1),SgT.Build(1,1,n);
}
int Install(int i)
{
int ans=0;
ans-=SgT.Sum(),ChangePath(i);
printf("%d ",ans);
return ans+SgT.Sum();
}
int Uninstall(int i)
{
int ans=0;
ans+=SgT.Sum(),ChangeSubtree(i);
printf("%d ",ans);
return ans-SgT.Sum();
}
private:
bool vis[MAXN];
int num,cnt,head[MAXN];
struct node
{
int v,d,ft,top,son,size,DFN;
}s[MAXN];
struct edge
{
int nxt,to;
edge(int nxt=0,int to=0):nxt(nxt),to(to){}
}e[MAXM];
class SegmentTree
{
public:
void Build(int i,int l,int r)
{
s[i]=node(l,r,0);
if(l==r)
{
s[i].v=0;
return;
}
int j=i<<1,mid=l+r>>1;
Build(j,l,mid),Build(j|1,mid+1,r),PushUp(i);
}
void Change(int i,int l,int r,bool v)
{
if(l==s[i].l && r==s[i].r)
{
Modify(i,v);
return;
}
if(s[i].lazy^10)
PushDown(i);
int j=i<<1,mid=s[i].l+s[i].r>>1;
if(r<=mid)
Change(j,l,r,v);
else if(l>mid)
Change(j|1,l,r,v);
else
Change(j,l,mid,v),Change(j|1,mid+1,r,v);
PushUp(i);
}
int Sum(void)
{
return s[1].v;
}
private:
struct node
{
int v,l,r,lazy;
node(int l=0,int r=0,int lazy=0):l(l),r(r),lazy(lazy){}
}s[MAXN<<2];
void Modify(int i,int v)
{
s[i].v=v ? s[i].r-s[i].l+1 : 0;
s[i].lazy=v;
}
void PushUp(int i)
{
int j=i<<1;
s[i].v=s[j].v+s[j|1].v;
}
void PushDown(int i)
{
int j=i<<1;
Modify(j,s[i].lazy),Modify(j|1,s[i].lazy);
s[i].lazy=10;
}
}SgT;
void AddEdge(int u,int v)
{
e[++cnt]=edge(head[u],v);
head[u]=cnt;
}
void AddEdges(int u,int v)
{
AddEdge(u,v),AddEdge(v,u);
}
void DFS1(int u,int k)
{
s[u].d=k,s[u].size=1;
for(int i=head[u],v;i;i=e[i].nxt)
if(!s[v=e[i].to].size)
{
DFS1(v,k+1);
s[v].ft=u,s[u].size+=s[v].size;
if(s[v].size>s[s[u].son].size)
s[u].son=v;
}
}
void DFS2(int u,int top)
{
s[u].top=top,s[u].DFN=++num,vis[u]=1;
if(s[u].son)
DFS2(s[u].son,top);
for(int i=head[u],v;i;i=e[i].nxt)
if(!vis[v=e[i].to])
DFS2(v,v);
}
void ChangePath(int x)
{
int a;
while((a=s[x].top)^1)
SgT.Change(1,s[a].DFN,s[x].DFN,1),x=s[a].ft;
SgT.Change(1,1,s[x].DFN,1);
}
void ChangeSubtree(int x)
{
SgT.Change(1,s[x].DFN,s[x].DFN+s[x].size-1,0);
}
}T;
int main(int argc,char *argv[])
{
scanf("%d",&n);
T.Init();
scanf("%d",&q);
for(int i=1,x;i<=q;++i)
{
char s[20];
scanf("\n%s %d",s,&x);
if(s[0]=='i')
printf("%d\n",T.Install(x+1));
else
printf("%d\n",T.Uninstall(x+1));
}
return 0;
}
谢谢阅读。