题目传送门
解题思路:
如果一个软件被卸载,那答案就是它所有已安装的子孙的个数;如果安装,就是它到根的链上没安装的个数.(注意修改lazy的时候)
AC代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 6 using namespace std; 7 8 int n,head[100001],rk[100001],tot,p,js,js2; 9 struct kkk { 10 int to,next; 11 }e[200001]; 12 struct dian { 13 int f,d,si,son,id,tp; 14 }q[100001]; 15 struct xianduan { 16 int l,r,v,lazy; 17 }a[400001]; 18 19 inline void add(int x,int y) { 20 e[++tot].to = y; 21 e[tot].next = head[x]; 22 head[x] = tot; 23 } 24 25 inline void dfs1(int rt,int fa,int deep) { 26 q[rt].d = deep; 27 q[rt].f = fa; 28 q[rt].si = 1; 29 q[rt].son = 0; 30 for(int i = head[rt];i; i = e[i].next) { 31 int u = e[i].to; 32 if(u == fa) continue; 33 dfs1(u,rt,deep + 1); 34 if(q[q[rt].son].si < q[u].si) q[rt].son = u; 35 q[rt].si += q[u].si; 36 } 37 } 38 39 inline void dfs2(int rt,int topf) { 40 q[rt].id = ++tot; 41 rk[tot] = rt; 42 q[rt].tp = topf; 43 if(q[rt].son == 0) return ; 44 dfs2(q[rt].son,topf); 45 for(int i = head[rt];i; i = e[i].next) { 46 int u = e[i].to; 47 if(u == q[rt].son || u == q[rt].f) continue; 48 dfs2(u,u); 49 } 50 } 51 52 inline void spr(int rt) { 53 if(a[rt].lazy == 0) return ; 54 if(a[rt].lazy == 1) { 55 a[rt*2].v = a[rt*2].r - a[rt*2].l + 1; 56 a[rt*2+1].v = a[rt*2+1].r - a[rt*2+1].l + 1; 57 } 58 if(a[rt].lazy == -1) { 59 a[rt*2].v = 0; 60 a[rt*2+1].v = 0; 61 } 62 a[rt*2].lazy = a[rt].lazy; 63 a[rt*2+1].lazy = a[rt].lazy; 64 a[rt].lazy = 0; 65 } 66 67 inline void build(int rt,int ll,int rr) { 68 a[rt].l = ll; 69 a[rt].r = rr; 70 a[rt].v = 0; 71 a[rt].lazy = 0; 72 if(ll == rr) return ; 73 int mid = (ll + rr) >> 1; 74 build(rt * 2,ll,mid); 75 build(rt * 2 + 1,mid + 1,rr); 76 } 77 78 inline int ssum(int rt,int L,int R) { 79 int oo = 0; 80 // printf("%d %d : %d ",a[rt].l,a[rt].r,a[rt].v); 81 if(a[rt].l >= L && a[rt].r <= R) 82 // printf("SD: %d ",a[rt].v); 83 return a[rt].v; 84 spr(rt); 85 int mid = a[rt].l + a[rt].r >> 1; 86 if(L <= mid) oo += ssum(rt * 2,L,R); 87 if(R > mid) oo += ssum(rt * 2 + 1,L,R); 88 // printf("OO : %d ",oo); 89 return oo; 90 } 91 92 inline int treeadd(int x,int y) { 93 int tx = q[x].tp; 94 int ty = q[y].tp; 95 int uu = 0; 96 while(tx != ty) { 97 uu += ssum(1,q[tx].id,q[x].id); 98 x = q[tx].f;tx = q[x].tp; 99 } 100 uu += ssum(1,q[y].id,q[x].id); 101 return uu; 102 } 103 104 inline void change(int rt,int L,int R) { 105 // printf("%d %d ",L,R);printf("FF : %d %d %d ",a[rt].l,a[rt].r,a[rt].v); 106 if(a[rt].l >= L && a[rt].r <= R) { 107 a[rt].lazy = 1; 108 a[rt].v = a[rt].r - a[rt].l + 1; 109 return ; 110 } 111 spr(rt); 112 int mid = a[rt].l + a[rt].r >> 1; 113 if(L <= mid) change(rt * 2,L,R); 114 if(R > mid) change(rt * 2 + 1,L,R); 115 a[rt].v = a[rt*2].v + a[rt*2+1].v; 116 117 } 118 119 inline void treechange(int x,int y) { 120 int tx = q[x].tp; 121 int ty = q[y].tp; 122 while(tx != ty) { 123 change(1,q[tx].id,q[x].id); 124 x = q[tx].f;tx = q[x].tp; 125 } 126 // if(q[x].d >= q[y].d) 127 change(1,q[y].id,q[x].id); 128 } 129 130 inline void change1(int rt,int L,int R) { 131 if(a[rt].l >= L && a[rt].r <= R) { 132 a[rt].lazy = -1; 133 a[rt].v = 0; 134 return ; 135 } 136 spr(rt); 137 int mid = a[rt].l + a[rt].r >> 1; 138 if(L <= mid) change1(rt * 2,L,R); 139 if(R > mid) change1(rt * 2 + 1,L,R); 140 a[rt].v = a[rt*2].v + a[rt*2+1].v; 141 // printf("%d %d : %d ",a[rt].l,a[rt].r,a[rt].v); 142 } 143 144 int main() { 145 // freopen("6.in.txt","r",stdin); 146 scanf("%d",&n); 147 for(int i = 2;i <= n; i++) { 148 int x; 149 scanf("%d",&x); 150 x++; 151 add(x,i); 152 } 153 dfs1(1,0,1); 154 tot = 0; 155 dfs2(1,1); 156 build(1,1,n); 157 scanf("%d",&p); 158 // for(int i = 1;i <= n; i++) 159 // printf("%d ",q[i].id); 160 for(int i = 1;i <= p; i++) { 161 string r; 162 cin >> r; 163 if(r == "install") { 164 int x; 165 scanf("%d",&x); 166 x++; 167 js = treeadd(x,1); 168 printf("%d ",q[x].d - js); 169 treechange(x,1); 170 } 171 else { 172 int x; 173 scanf("%d",&x); 174 x++; 175 js2 = ssum(1,q[x].id,q[x].id + q[x].si - 1); 176 printf("%d ",js2); 177 change1(1,q[x].id,q[x].id + q[x].si - 1); 178 } 179 } 180 return 0; 181 }