【洛谷P2146】【LOJ#2130】【BZOJ4196】软件包管理器【树链剖分】

本文主要是介绍【洛谷P2146】【LOJ#2130】【BZOJ4196】软件包管理器【树链剖分】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

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

你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。如果软件包A依赖软件包B，那么安装软件包A以前，必须先安装软件包B。同时，如果想要卸载软件包B，则必须卸载软件包A。现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除0号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而0号软件包不依赖任何一个软件包。依赖关系不存在环（若有m(m≥2)个软件包A1,A2,A3,…,Am，其中A1依赖A2，A2依赖A3，A3依赖A4，……，Am−1依赖Am，而Am依赖A1，则称这m个软件包的依赖关系构成环），当然也不会有一个软件包依赖自己。
现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为0。

思路：

默写树剖板子 $q w q$

显然，删除一个软件 $x$ 就相当于要删除所有依赖他的软件，也就是求 $x$ 的子树大小；增加一个软件 $x$ 就相当于要把路径 $1 - x$ 全部增加，即求一条路径的节点个数。
每一次都修改树显然是不够优秀的。我们可以考虑直接把树建好，然后每一个节点维护一个权值 $0 / 1$ ，表示这个节点现在是否真实存在。
删除一个节点就只要求出以该节点为根的子树内权值为1的节点个数，增加一个节点就只要求路径 $1 - x$ 的权值为0的点的个数。
那么问题就是一个树剖的板子了。线段树维护区间和，每次询问之后打一个 $l a z y$ 标记即可。
感觉现在做的树剖题目都很裸啊，到时候要拐一点弯的题就完了啊 $q w q$ 。
时间复杂度 $O(n\log^2 n)$

代码：

成功写进 $150$ 行233

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int N=200010;
int fa[N],son[N],dep[N],top[N],size[N],id[N],head[N];
int n,tot,cnt,m,x;
char ch[20];struct edge
{int next,to;
}e[N];struct Treenode
{int l,r,sum,lazy;
};struct Tree
{Treenode tree[N*4];void pushdown(int x){if (tree[x].lazy!=-1){tree[x*2].lazy=tree[x*2+1].lazy=tree[x].lazy;if (!tree[x].lazy) tree[x*2].sum=tree[x*2+1].sum=0;else{tree[x*2].sum=tree[x*2].r-tree[x*2].l+1;tree[x*2+1].sum=tree[x*2+1].r-tree[x*2+1].l+1;}tree[x].lazy=-1;}}void pushup(int x){tree[x].sum=tree[x*2].sum+tree[x*2+1].sum;}void build(int x){tree[x].lazy=-1;if (tree[x].l==tree[x].r) return;int mid=(tree[x].l+tree[x].r)>>1;tree[x*2].l=tree[x].l;tree[x*2].r=mid;tree[x*2+1].l=mid+1;tree[x*2+1].r=tree[x].r;build(x*2); build(x*2+1);}int update(int x,int l,int r,int val){if (tree[x].l==l && tree[x].r==r){int s=tree[x].sum;tree[x].lazy=val;if (!val) tree[x].sum=0;else tree[x].sum=tree[x].r-tree[x].l+1;return s;}pushdown(x);int mid=(tree[x].l+tree[x].r)>>1,ans=0;if (r<=mid) ans=update(x*2,l,r,val);else if (l>mid) ans=update(x*2+1,l,r,val);else ans=update(x*2,l,mid,val)+update(x*2+1,mid+1,r,val);pushup(x);return ans;}
}Tree;void add(int from,int to)
{e[++tot].to=to;e[tot].next=head[from];head[from]=tot;
}void dfs1(int x)
{size[x]=1; dep[x]=dep[fa[x]]+1;for (int i=head[x];~i;i=e[i].next){int y=e[i].to;dfs1(y);size[x]+=size[y];if (size[y]>size[son[x]]) son[x]=y;}
}void dfs2(int x,int tp)
{top[x]=tp; id[x]=++cnt;if (son[x]) dfs2(son[x],tp);for (int i=head[x];~i;i=e[i].next){int y=e[i].to;if (y!=son[x]) dfs2(y,y);}
}int insert(int x,int y)
{int sum=0;while (top[x]!=top[y]){if (dep[top[x]]<dep[top[y]]) swap(x,y);sum+=id[x]-id[top[x]]+1-Tree.update(1,id[top[x]],id[x],1);x=fa[top[x]];}if (dep[x]<dep[y]) swap(x,y);sum+=id[x]-id[y]+1-Tree.update(1,id[y],id[x],1);return sum;
}int del(int x)
{return Tree.update(1,id[x],id[x]+size[x]-1,0);
}int main()
{memset(head,-1,sizeof(head));scanf("%d",&n);for (int i=2;i<=n;i++){scanf("%d",&fa[i]);fa[i]++;add(fa[i],i);}dfs1(1); dfs2(1,1);Tree.tree[1].l=1; Tree.tree[1].r=n;Tree.build(1);scanf("%d\n",&m);while (m--){scanf("%s%d",ch+1,&x);x++;if (ch[1]=='i')printf("%d\n",insert(1,x));elseprintf("%d\n",del(x));}return 0;
}