[NOIP模拟46]鼠树

本文主要是介绍[NOIP模拟46]鼠树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

神仙题。

首先不考虑把黑点变白，发现每个白点的信息与它的归属点是相同的。可以在线段树中只维护黑点的信息，再记录$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 }

这篇关于[NOIP模拟46]鼠树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！