神仙题。
首先不考虑把黑点变白,发现每个白点的信息与它的归属点是相同的。可以在线段树中只维护黑点的信息,再记录$DFS$序上每个点之前黑点个数的前缀和,每次操作可以二分出该点的归属点进行操作。
具体维护黑点管辖点的个数与它的权值,及前两者乘积之和。一些其他的点数可以通过子树大小减管辖点总和得到。两个修改操作直接线段树上修改即可。
再考虑黑点变白的情况。每次把黑点变白后,它管辖点的归属点改变,但权值不变,可以在线段树中记录下当前点真实权值与它归属点权值的差,删点时做子树加,每次询问用归属点的权值加上这个差值。
但这个点的子树中还有归属点不变的点,通过$4$操作再把多加上的权值减掉。
1 #include<bits/stdc++.h> 2 #define int unsigned int 3 using namespace std; 4 5 namespace IO{ 6 inline int read(){ 7 int x=0,f=1; char ch=getchar(); 8 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } 9 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } 10 return x*f; 11 } 12 inline void write(int x,char sp){ 13 char ch[20]; int len=0; 14 if(x<0){ putchar('-'); x=~x+1; } 15 do{ ch[len++]=x%10+(1<<5)+(1<<4); x/=10; }while(x); 16 for(int i=len-1;~i;i--) putchar(ch[i]); putchar(sp); 17 } 18 } using namespace IO; 19 20 const int NN=3e5+5; 21 int n,m,idx,to[NN<<1],nex[NN<<1],head[NN],col[NN]; 22 int opt,k,w; 23 inline void add(int a,int b){ 24 to[++idx]=b; nex[idx]=head[a]; head[a]=idx; 25 to[++idx]=a; nex[idx]=head[b]; head[b]=idx; 26 } 27 28 namespace BIT{ 29 struct bit{ 30 int c[NN]; 31 inline void insert(signed pos,int x){ 32 while(pos<=n){ 33 c[pos]+=x; 34 pos+=(pos&(-pos)); 35 } 36 } 37 inline int query(signed pos){ 38 int res=0; 39 while(pos){ 40 res+=c[pos]; 41 pos-=(pos&(-pos)); 42 } 43 return res; 44 } 45 }bl; 46 } using namespace BIT; 47 48 namespace segment_tree{ 49 #define ld rt<<1 50 #define rd (rt<<1)|1 51 int num[NN<<2],val[NN<<2],sum[NN<<2],ch[NN<<2],laz[NN<<2],lac[NN<<2]; 52 inline void pushup(int rt){ 53 num[rt]=num[ld]+num[rd]; 54 sum[rt]=sum[ld]+sum[rd]; 55 val[rt]=val[ld]+val[rd]; 56 ch[rt]=ch[ld]+ch[rd]; 57 } 58 inline void pushdown(int rt,int l,int r){ 59 if(laz[rt]){ 60 sum[ld]+=laz[rt]*num[ld]; sum[rd]+=laz[rt]*num[rd]; 61 val[ld]+=laz[rt]; val[rd]+=laz[rt]; 62 laz[ld]+=laz[rt]; laz[rd]+=laz[rt]; 63 } 64 if(lac[rt]){ 65 int mid=l+r>>1; 66 ch[ld]+=lac[rt]*(mid-l+1); ch[rd]+=lac[rt]*(r-mid); 67 lac[ld]+=lac[rt]; lac[rd]+=lac[rt]; 68 } 69 laz[rt]=lac[rt]=0; 70 } 71 void insert(int rt,int l,int r,int pos,int nu,int v){ 72 if(l==r){ 73 num[rt]=nu; val[rt]=v; sum[rt]=nu*v; 74 return; 75 } 76 pushdown(rt,l,r); 77 int mid=l+r>>1; 78 if(pos<=mid) insert(ld,l,mid,pos,nu,v); 79 else insert(rd,mid+1,r,pos,nu,v); 80 pushup(rt); 81 } 82 void delet(int rt,int l,int r,int pos){ 83 if(l==r){ 84 sum[rt]=num[rt]=val[rt]=0; 85 return; 86 } 87 pushdown(rt,l,r); 88 int mid=l+r>>1; 89 if(pos<=mid) delet(ld,l,mid,pos); 90 else delet(rd,mid+1,r,pos); 91 pushup(rt); 92 } 93 void update(int rt,int l,int r,int opl,int opr,int v){ 94 if(l>=opl&&r<=opr){ 95 val[rt]+=v; 96 sum[rt]+=v*num[rt]; 97 laz[rt]+=v; 98 return; 99 } 100 pushdown(rt,l,r); 101 int mid=l+r>>1; 102 if(opl<=mid) update(ld,l,mid,opl,opr,v); 103 if(opr>mid) update(rd,mid+1,r,opl,opr,v); 104 pushup(rt); 105 } 106 void modify(int rt,int l,int r,int opl,int opr,int v){//差 107 if(l>=opl&&r<=opr){ 108 ch[rt]+=v*(r-l+1); 109 lac[rt]+=v; 110 return; 111 } 112 pushdown(rt,l,r); 113 int mid=l+r>>1; 114 if(opl<=mid) modify(ld,l,mid,opl,opr,v); 115 if(opr>mid) modify(rd,mid+1,r,opl,opr,v); 116 pushup(rt); 117 } 118 int queryc(int rt,int l,int r,int opl,int opr){ 119 if(l>=opl&&r<=opr) return ch[rt]; 120 pushdown(rt,l,r); 121 int mid=l+r>>1; int ans=0; 122 if(opl<=mid) ans+=queryc(ld,l,mid,opl,opr); 123 if(opr>mid) ans+=queryc(rd,mid+1,r,opl,opr); 124 return ans; 125 } 126 int querys(int rt,int l,int r,int opl,int opr){ 127 if(l>=opl&&r<=opr) return sum[rt]; 128 pushdown(rt,l,r); 129 int mid=l+r>>1; int ans=0; 130 if(opl<=mid) ans+=querys(ld,l,mid,opl,opr); 131 if(opr>mid) ans+=querys(rd,mid+1,r,opl,opr); 132 return ans; 133 } 134 int queryn(int rt,int l,int r,int opl,int opr){ 135 if(l>=opl&&r<=opr) return num[rt]; 136 pushdown(rt,l,r); 137 int mid=l+r>>1; int ans=0; 138 if(opl<=mid) ans+=queryn(ld,l,mid,opl,opr); 139 if(opr>mid) ans+=queryn(rd,mid+1,r,opl,opr); 140 return ans; 141 } 142 int queryv(int rt,int l,int r,int pos){ 143 if(l==r) return val[rt]; 144 pushdown(rt,l,r); 145 int mid=l+r>>1; 146 if(pos<=mid) return queryv(ld,l,mid,pos); 147 if(pos>mid) return queryv(rd,mid+1,r,pos); 148 } 149 } using namespace segment_tree; 150 151 namespace Tree_Division{ 152 int dep[NN],dfn[NN],id[NN],top[NN],fa[NN],siz[NN],son[NN],cnt; 153 void dfs1(int s,int f){ 154 fa[s]=f; siz[s]=1; dep[s]=dep[f]+1; 155 for(int i=head[s];i;i=nex[i]){ 156 int v=to[i]; 157 if(v==f) continue; 158 dfs1(v,s); 159 siz[s]+=siz[v]; 160 if(siz[son[s]]<siz[v]) son[s]=v; 161 } 162 } 163 void dfs2(int s,int t){ 164 top[s]=t; dfn[s]=++cnt; id[cnt]=s; 165 if(!son[s]) return; 166 dfs2(son[s],t); 167 for(int i=head[s];i;i=nex[i]){ 168 int v=to[i]; 169 if(v!=fa[s]&&v!=son[s]) dfs2(v,v); 170 } 171 } 172 inline int getown(int x){ 173 if(col[x]) return x; 174 while(x){ 175 if(bl.query(dfn[x])-bl.query(dfn[top[x]]-1)==0){ x=fa[top[x]]; continue; } 176 if(col[x]) return x; 177 int res,l=dfn[top[x]],r=dfn[x]; 178 while(l<=r){ 179 int mid=l+r>>1; 180 if(bl.query(dfn[x])-bl.query(mid-1)) res=mid, l=mid+1; 181 else r=mid-1; 182 } 183 return id[res]; 184 } 185 return 1; 186 } 187 } using namespace Tree_Division; 188 189 signed main(){ 190 // freopen("pastel2.in","r",stdin); 191 // freopen("out","w",stdout); 192 n=read(); m=read(); 193 for(int i=2;i<=n;i++) add(read(),i); 194 dfs1(1,0); dfs2(1,1); insert(1,1,n,1,siz[1],0); bl.insert(1,1); col[1]=1; 195 while(m--){ 196 opt=read(); k=read(); if(opt==2||opt==4) w=read(); 197 if(opt==1){ 198 int tmp=getown(k); 199 write(queryv(1,1,n,dfn[tmp])+queryc(1,1,n,dfn[k],dfn[k]),'\n'); 200 } 201 if(opt==2) update(1,1,n,dfn[k],dfn[k],w); 202 if(opt==3){ 203 int res=0; 204 int tmp=getown(k); 205 if(!col[k]) res+=queryv(1,1,n,dfn[tmp])*(siz[k]-queryn(1,1,n,dfn[k],dfn[k]+siz[k]-1)); 206 res+=querys(1,1,n,dfn[k],dfn[k]+siz[k]-1)+queryc(1,1,n,dfn[k],dfn[k]+siz[k]-1); 207 write(res,'\n'); 208 } 209 if(opt==4) update(1,1,n,dfn[k],dfn[k]+siz[k]-1,w); 210 if(opt==5){ 211 int tmp=getown(k),numm=siz[k]-queryn(1,1,n,dfn[k],dfn[k]+siz[k]-1); 212 int vall=queryv(1,1,n,dfn[tmp]); 213 col[k]=1; 214 insert(1,1,n,dfn[k],numm,vall); 215 insert(1,1,n,dfn[tmp],queryn(1,1,n,dfn[tmp],dfn[tmp])-numm,vall); 216 bl.insert(dfn[k],1); 217 } 218 if(opt==6){ 219 int size=queryn(1,1,n,dfn[k],dfn[k]); 220 col[k]=0; bl.insert(dfn[k],-1); 221 int tmp=getown(k),ww=queryv(1,1,n,dfn[k])-queryv(1,1,n,dfn[tmp]); 222 insert(1,1,n,dfn[tmp],queryn(1,1,n,dfn[tmp],dfn[tmp])+size,queryv(1,1,n,dfn[tmp])); 223 modify(1,1,n,dfn[k],dfn[k]+siz[k]-1,ww); 224 delet(1,1,n,dfn[k]); 225 update(1,1,n,dfn[k],dfn[k]+siz[k]-1,-ww); 226 } 227 } 228 return 0; 229 }View Code