题目大意：
有n个软件安装包，除第一个以外，其他的要在另一个安装包的基础上安装，且无环，问在安装和卸载某个软件包时，这个操作实际上会改变多少个软件包的安装状态。
思路：
可构成树，用树链剖分，线段树。已安装的为1，未安装的为0。对于安装操作，就是询问x到0的路径上0的个数，然后把这个路径赋为1；对于卸载操作，就是询问x的子树中1的个数，然后把子树赋为0。
代码：
1 #include<cstdio> 2 #include<iostream> 3 #define M 800500 4 using namespace std; 5 6 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]; 7 8 void ins(int x,int y) 9 { 10 to[++cnt]=y,next[cnt]=head[x],head[x]=cnt; 11 } 12 13 void dfs1(int x) 14 { 15 size[x]=1; 16 for (int i=head[x];i;i=next[i]) 17 if (to[i]!=pa[x]) 18 { 19 pa[to[i]]=x,deep[to[i]]=deep[x]+1; 20 dfs1(to[i]),size[x]+=size[to[i]]; 21 if (size[to[i]]>size[hson[x]]) hson[x]=to[i]; 22 } 23 } 24 25 void dfs2(int x,int tp) 26 { 27 id[x]=++dfn,top[x]=tp; 28 if (hson[x]) dfs2(hson[x],tp); 29 for (int i=head[x];i;i=next[i]) 30 if (to[i]!=pa[x]&&to[i]!=hson[x]) dfs2(to[i],to[i]); 31 last[x]=dfn; 32 } 33 34 void build(int l,int r,int cur) 35 { 36 if (l==r) { sum[cur]=0,lazy[cur]=-1,sz[cur]=1; return; } 37 int mid=l+r>>1; 38 build(l,mid,cur<<1),build(mid+1,r,cur<<1|1); 39 sz[cur]=sz[cur<<1]+sz[cur<<1|1]; 40 } 41 42 void push_down(int k) 43 { 44 if (lazy[k]!=-1) 45 { 46 sum[k<<1]=sz[k<<1]*lazy[k],sum[k<<1|1]=sz[k<<1|1]*lazy[k]; 47 lazy[k<<1]=lazy[k<<1|1]=lazy[k],lazy[k]=-1; 48 } 49 } 50 51 void change(int L,int R,int l,int r,int cur,int val) 52 { 53 if (L==l && R==r) { sum[cur]=val*sz[cur]; lazy[cur]=val; return; } 54 int mid=L+R>>1; push_down(cur); 55 if (r<=mid) change(L,mid,l,r,cur<<1,val); 56 else if (l>mid) change(mid+1,R,l,r,cur<<1|1,val); 57 else change(L,mid,l,mid,cur<<1,val),change(mid+1,R,mid+1,r,cur<<1|1,val); 58 sum[cur]=sum[cur<<1]+sum[cur<<1|1]; 59 } 60 61 int ask(int L,int R,int l,int r,int cur) 62 { 63 if (L==l && R==r) return sum[cur]; 64 int mid=L+R>>1; push_down(cur); 65 if (r<=mid) return ask(L,mid,l,r,cur<<1); 66 else if (l>mid) return ask(mid+1,R,l,r,cur<<1|1); 67 else return ask(L,mid,l,mid,cur<<1)+ask(mid+1,R,mid+1,r,cur<<1|1); 68 } 69 70 void add(int x,int y) 71 { 72 if (deep[x]<deep[y]) swap(x,y); 73 int sum=0,t=deep[x]-deep[y]+1; 74 for (;top[x]!=top[y];x=pa[top[x]]) 75 { 76 if (deep[top[x]]<deep[top[y]]) swap(x,y); 77 sum+=ask(1,n,id[top[x]],id[x],1); 78 change(1,n,id[top[x]],id[x],1,1); 79 } 80 if (deep[x]>deep[y]) swap(x,y); 81 sum+=ask(1,n,id[x],id[y],1); 82 change(1,n,id[x],id[y],1,1); 83 printf("%d\n",t-sum); 84 } 85 86 int main() 87 { 88 int i,m,x; 89 scanf("%d",&n); 90 for (i=1;i<n;i++) scanf("%d",&m),ins(m+1,i+1); 91 scanf("%d",&m),dfs1(1),dfs2(1,1),build(1,n,1); 92 for (i=1;i<=m;i++) 93 { 94 char ch[20]; 95 scanf("%s%d",ch,&x),x++; 96 if (ch[0]=='i') add(1,x); 97 else printf("%d\n",ask(1,n,id[x],last[x],1)),change(1,n,id[x],last[x],1,0); 98 } 99 return 0; 100 }转载于:https://www.cnblogs.com/HHshy/p/5823371.html
