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，……，A[m-1]依赖Am，而Am依赖A1，则称这m个软件包的依赖关系构成环），当然也不会有一个软件包依赖自己。
现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为0。
输入格式：
从文件manager.in中读入数据。
输入文件的第1行包含1个整数n，表示软件包的总数。软件包从0开始编号。
随后一行包含n?1个整数，相邻整数之间用单个空格隔开，分别表示1,2,3,?,n?2,n?1号软件包依赖的软件包的编号。
接下来一行包含1个整数q，表示询问的总数。之后q行，每行1个询问。询问分为两种：
install x：表示安装软件包x
uninstall x：表示卸载软件包x
你需要维护每个软件包的安装状态，一开始所有的软件包都处于未安装状态。
对于每个操作，你需要输出这步操作会改变多少个软件包的安装状态，随后应用这个操作（即改变你维护的安装状态）。
输出格式：
输出到文件manager.out中。
输出文件包括q行。
输出文件的第i行输出1个整数，为第i步操作中改变安装状态的软件包数。
对于安装操作就是把该节点到根的路径中的每个节点变为1
对于删除操作就是把子树赋为0
树链剖分
#include<bits/stdc++.h> using namespace std; #define MAXN 1000010 inline int read() { int f=1,x=0; char ch; do { ch=getchar(); if(ch==‘-‘) f=-1; }while(ch<‘0‘||ch>‘9‘); do { x=(x<<3)+(x<<1)+ch-‘0‘; ch=getchar(); }while(ch>=‘0‘&&ch<=‘9‘); return f*x; } struct node { int to; int next; }; int n; node g[MAXN*2]; int head[MAXN],cnt; int fa[MAXN],tot[MAXN],son[MAXN],dep[MAXN]; int top[MAXN],num[MAXN],h=0; int add[MAXN*4]={-1}; inline void addedge(int a,int b) { ++cnt;g[cnt].to=b;g[cnt].next=head[a];head[a]=cnt;return; } inline void dfs(int x,int f) { son[x]=0;tot[x]=1; for(int i=head[x];i;i=g[i].next) { int v=g[i].to; if(v!=f) { fa[v]=x; dep[v]=dep[x]+1; dfs(v,x); if(tot[v]>tot[son[x]]) son[x]=v; tot[x]+=tot[v]; } } return; } inline void dfs2(int x,int now) { top[x]=now;num[x]=++h; if(son[x]) dfs2(son[x],now); for(int i=head[x];i;i=g[i].next) { int v=g[i].to; if(v!=son[x]&&v!=fa[x]) dfs2(v,v); } } struct s_tree { int l; int r; int sum; inline int mid() { return(l+r)>>1; } }tree[MAXN<<2]; #define lc o<<1 #define rc o<<1|1 inline void build(int o,int l,int r) { tree[o].l=l;tree[o].r=r;tree[o].sum=0; if(l==r) return; else { int mid=tree[o].mid(); build(lc,l,mid); build(rc,mid+1,r); } } inline void pushdown(int o) { add[lc]=add[o]; add[rc]=add[o]; tree[lc].sum=(tree[lc].r-tree[lc].l+1)*add[o]; tree[rc].sum=(tree[rc].r-tree[rc].l+1)*add[o]; add[o]=-1; } inline void update(int o,int x,int y,int z) { int l=tree[o].l,r=tree[o].r; if(x<=l&&y>=r) { add[o]=z; tree[o].sum=(tree[o].r-tree[o].l+1)*add[o]; return; } else { if(add[o]!=-1) pushdown(o); if(x>r||y<l) return; update(lc,x,y,z); update(rc,x,y,z); tree[o].sum=tree[lc].sum+tree[rc].sum; } } inline int query(int o,int x,int y) { int l=tree[o].l,r=tree[o].r; if(x<=l&&y>=r) return tree[o].sum; else { if(x>r||y<l) return 0; if(add[o]!=-1) pushdown(o); return query(lc,x,y)+query(rc,x,y); } } inline void change(int a,int b) { int ta=top[a],tb=top[b]; while(ta!=tb) { if(dep[ta]<dep[tb]) swap(ta,tb),swap(a,b); update(1,num[ta],num[a],1); a=fa[ta];ta=top[a]; } if(a==b) update(1,num[a],num[b],1); else{ if(dep[a]<dep[b]) swap(a,b); update(1,num[b],num[a],1); } } int main() { n=read(); for(int i=1;i<n;i++) { int x=read();x++; addedge(x,i+1); addedge(i+1,x); } fa[1]=0;dep[1]=1; dfs(1,0); dfs2(1,1); build(1,1,h); int q=read(); for(int i=1;i<=q;i++) { string opt;cin>>opt;int x=read();x++; if(opt[0]==‘i‘) { int ans1=query(1,num[1],num[x]); change(1,x); int ans2=query(1,num[1],num[x]); printf("%d\n",abs(ans2-ans1)); } else { int ans1=query(1,num[x],num[x]+tot[x]-1); update(1,num[x],num[x]+tot[x]-1,0); int ans2=query(1,num[x],num[x]+tot[x]-1); printf("%d\n",abs(ans2-ans1)); } } }
原文：https://www.cnblogs.com/wlzs1432/p/9370877.html