COJ 0981 WZJ 의 데이터 구조 (마이너스 19) 트 리 종합
52639 단어 데이터 구조
WZJ 의 데이터 구조 (마이너스 19)
난이도 레벨: E;운행 시간 제한: 3500 ms;운행 공간 제한: 262144KB;코드 길이 제한: 2000000 B
시험 문제 설명
WZJ 의 데이터 구조 에는 나무 에 관 한 것 이 많다.이것 은 많은 연습 템 플 릿 의 학우 들 이 찾 아 다 니 는 것 을 매우 불쾌 하 게 만 들 었 다. 그래서 WZJ 는 아이들 과 함께 이 문제 들 을 어떻게 한데 모 을 것 인 가 를 상의 했다.
WZJ: 여러분 의 간단 함 을 위해 서 저 는 처음에 뿌리 가 있 는 나무 라 고 규 정 했 습 니 다.
LZJ: 그럼 내 가 꼭 바 꿔 야 겠 네.
XJR: 체인 정보 수정, 체인 정보 증가, 체인 정보 배가, 유지 체인 정보의 최대, 최소, 총 화 는 잘 될 것 입 니 다.
CHX: 하위 트 리 정보 수정, 하위 트 리 정보 증가, 하위 트 리 정보 배가, 하위 트 리 정보의 최대, 최소, 총 화 를 유지 하 는 것 도 좋 습 니 다.
WZJ: 그럼 이 문 제 는 너무 물 과 같 군요. 우 리 는 나무의 형 태 를 수시로 바 꿀 수 있어 야 합 니 다. 아버 지 를 바 꾸 는 조작 을 추가 하 세 요.
CHX: 그것 도 충분히 물 입 니 다. 아버지 에 대한 조 회 를 하나 더 하 겠 습 니 다.
LZJ: 어렵 게 종합 문 제 를 냈 는데 하위 트 리 에서 작 동 하 는 지 확인 해 보 세 요.
XJR: 오프라인 을 꼭 끊 어야 하 는 거 죠?
입력
이 문 제 는 모두 22 개의 조작 이 있다.
첫 번 째 줄 은 N 과 M 입 니 다. 이 나무 가 있 으 면 N 점 M 이 있 음 을 표시 합 니 다.
그 다음 N - 1 줄, 각 줄 x, y 는 x - y 에 한 변 이 있다 는 것 을 나타 낸다.
다음은 N 줄 이 고 줄 마다 숫자 로 각 점 의 가중치 를 표시 합 니 다.
뒷줄
다음은 M 행.
첫 번 째 숫자 는 K 입 니 다.
K=0 뿌리 를 바꾸다
K=1 고치다 점 x 의 가중치 를 y 로 바 꾸 는 것 을 나타 낸다.
K=2 더 하 다 점 x 의 가중치 를 y 증가 시 키 는 것 을 나타 낸다.
K=3 에서 점 x 의 가중치 를 y 배로 늘 리 는 것 을 나타 낸다.
K=4 질문 이 점 의 가 치 를 묻 는 것 을 나타 낸다.
K=5 체인 수정, 뒤에 x, y, z 를 표시 합 니 다. 이 나무 에서 x - y 의 경로 상 점 값 을 z 로 바 꾸 는 것 을 표시 합 니 다.
K=6 체인 증가, 뒤에 x, y, z 를 표시 합 니 다.
K=7 이 나무 에서 x - y 의 경 로 를 z 배로 늘 리 는 것 을 나타 낸다.
K=8 체인 문의 min, 뒤에 x, y 를 표시 합 니 다. 이 나무 에서 x - y 의 경 로 를 묻 는 min 을 표시 합 니 다.
K=9 체인 문의 max, 뒤에 x, y 를 표시 합 니 다. 이 나무 에서 x - y 의 경 로 를 묻 는 max 를 표시 합 니 다.
K=10 체인 문의 sum, 뒤에 x, y 를 표시 합 니 다. 이 나무 에서 x - y 의 경 로 를 묻 는 sum 을 표시 합 니 다.
K=11 체인 문의 siz, 뒤에 x, y 를 표시 합 니 다.
K=12 하위 트 리 수정, 뒤에 x, y 를 표시 하고 x 를 뿌리 로 하 는 하위 트 리 의 점 값 을 y 로 변경 합 니 다.
K=13 하위 트 리 증가, 뒤쪽 x, y 를 나타 내 며 x 를 뿌리 로 하 는 하위 트 리 의 점 가중치 증가 y 를 나타 낸다.
K=14 하위 나무 가 배가 되 었 음 을 나타 내 고, 뒤에 x, y 는 x 를 뿌리 로 하 는 하위 나무의 점 값 이 y 배가 되 었 음 을 나타 낸다.
K=15 하위 트 리 문의 min, 뒤에 x, x 를 뿌리 로 하 는 하위 트 리 의 점 을 묻 는 min
K=16 하위 트 리 질문 max, 뒤 x, x 를 뿌리 로 하 는 하위 트 리 의 점 을 묻 는 max
K=17 하위 트 리 질문 sum, 뒤에 x, x 를 뿌리 로 하 는 하위 트 리 의 점 을 묻 는 sum 을 표시 합 니 다.
K=18 하위 트 리 가 siz, 뒤에 x 를 묻 는 것 은 x 를 뿌리 로 하 는 하위 트 리 의 점 이 얼마나 되 는 지 묻 는 것 을 나타 낸다.
K=19 하면, 만약, 만약...
K=20 하위 트 리, 뒤에 x, y, y 가 x 의 하위 트 리 에 있 는 지 물 어보 고 true / false 를 출력 합 니 다.
K=21 아버지
출력
질문 마다 답 을 하나씩 출력 합 니 다.
예제 입력
5 301 22 33 44 51 -2 3 -1 230 21 2 22 3 13 5 54 25 3 2 56 1 4 37 4 5 28 5 39 2 510 1 511 3 412 4 -313 2 -114 3 415 216 217 418 419 4 120 1 421 114 1 415 318 119 5 321 513 3 14 517 2
출력 예시
2420442-1628-322true728328-63-79
기타 설명
N, M < = 100000, 모든 계산 결 과 는 log 로 보장 합 니 다. long 범위 내.
문제 풀이: 물이 야. AAA 나무 다 됐어.(내 가 switch 를 2 점 으로 바 꿔 서 찾 으 면 좀 빠 르 지 않 을 까 하하)
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 #include<algorithm>
5 #include<queue>
6 #include<cstring>
7 #define PAU putchar(' ')
8 #define ENT putchar('
')
9 #define CH for(int d=0;d<=1;d++) if(ch[d])
10 using namespace std;
11 const int maxn=100000+10,inf=1<<29;
12 struct info{long long mi,mx,siz,sm;}null=(info){inf,-inf,0,0};
13 struct tag{int mul,add;bool empty(){return (mul==1&&add==0);}}nulltag=(tag){1,0};
14 info operator+(const info&a,const info&b){
15 return (info){min(a.mi,b.mi),max(a.mx,b.mx),a.siz+b.siz,a.sm+b.sm};
16 }
17 info operator+(const info&a,const tag&b){
18 return a.siz?(info){a.mi*b.mul+b.add,a.mx*b.mul+b.add,a.siz,a.sm*b.mul+b.add*a.siz}:null;
19 }
20 tag operator+(const tag&a,const tag&b){
21 return (tag){a.mul*b.mul,a.add*b.mul+b.add};
22 }
23 struct snode{
24 snode*ch[2],*fa;
25 info x,sm;tag od,all;
26 void init(){x=sm=null;od=all=nulltag;ch[0]=ch[1]=fa=NULL;return;}
27 snode(){x=sm=null;od=all=nulltag;ch[0]=ch[1]=fa=NULL;}
28 void addt(tag a){
29 od=od+a;all=all+a;x=x+a;sm=sm+a;return;
30 }
31 void down(){
32 if(!od.empty()){CH{ch[d]->addt(od);};od=nulltag;}return;
33 }
34 void update(){
35 sm=x;CH{sm=sm+ch[d]->sm;}return;
36 }
37 }Splay[maxn],*root[maxn];
38 int parent(snode*x,snode*&y){return (y=x->fa)?y->ch[1]==x?1:y->ch[0]==x?0:-1:-1;}
39 static void rotate(snode*x){
40 snode*y,*z;int d1=parent(x,y),d2=parent(y,z);
41 if(y->ch[d1]=x->ch[d1^1]) y->ch[d1]->fa=y;
42 y->fa=x;x->fa=z;x->ch[d1^1]=y;
43 if(d2!=-1) z->ch[d2]=x;
44 y->update();return;
45 }
46 void pushdown(snode*x){
47 static snode*s[maxn];int top=0;
48 for(snode*y;;x=y){
49 s[top++]=x;y=x->fa;
50 if(!y||(y->ch[0]!=x&&y->ch[1]!=x)) break;
51 } while(top--) s[top]->down();return;
52 }
53 static snode*splay(snode*x){
54 pushdown(x);snode*y,*z;int d1,d2;
55 while(true){
56 if((d1=parent(x,y))<0) break;
57 if((d2=parent(y,z))<0){rotate(x);break;}
58 if(d1==d2) rotate(y),rotate(x);
59 else rotate(x),rotate(x);
60 } x->update();return x;
61 }
62 snode*join(snode*x,snode*y){
63 if(!x)return y;if(!y)return x;
64 while(x->ch[1]) x->down(),x=x->ch[1];
65 splay(x)->ch[1]=y;y->fa=x;x->update();return x;
66 }
67 struct node{
68 node*ch[2],*fa,*s[2];
69 info x,sm,sb,all;tag cha,tre;bool rev;
70 int id;
71 void revt(){
72 swap(ch[0],ch[1]);swap(s[0],s[1]);rev^=1;return;
73 }
74 void chat(tag a){
75 x=x+a;sm=sm+a;cha=cha+a;all=sm+sb;return;
76 }
77 void tret(tag a){
78 tre=tre+a;sb=sb+a;all=sm+sb;if(root[id])root[id]->addt(a);return;
79 }
80 void down(){
81 if(rev){CH{ch[d]->revt();}rev=false;}
82 if(!cha.empty()){CH{ch[d]->chat(cha);}cha=nulltag;}
83 if(!tre.empty()){CH{ch[d]->tret(tre);}tre=nulltag;}
84 return;
85 }
86 void update(){
87 sm=x;sb=null;
88 if(root[id])sb=sb+root[id]->sm;
89 CH{sm=sm+ch[d]->sm;sb=sb+ch[d]->sb;}
90 all=sm+sb;
91 s[0]=ch[0]?ch[0]->s[0]:this;
92 s[1]=ch[1]?ch[1]->s[1]:this;
93 return;
94 }
95 }lct[maxn];
96 int parent(node*x,node*&y){return (y=x->fa)?y->ch[1]==x?1:y->ch[0]==x?0:-1:-1;}
97 void rotate(node*x){
98 node*y,*z;int d1=parent(x,y),d2=parent(y,z);
99 if(y->ch[d1]=x->ch[d1^1]) y->ch[d1]->fa=y;
100 y->fa=x;x->fa=z;x->ch[d1^1]=y;
101 if(d2!=-1) z->ch[d2]=x;
102 y->update();return;
103 }
104 void pushdown(node*x){
105 static node*s[maxn];int top=0;
106 for(node*y;;x=y){
107 s[top++]=x;y=x->fa;
108 if(!y||(y->ch[0]!=x&&y->ch[1]!=x)) break;
109 } while(top--) s[top]->down();return;
110 }
111 node*splay(node*x){
112 pushdown(x);node*y,*z;int d1,d2;
113 while(true){
114 if((d1=parent(x,y))<0) break;
115 if((d2=parent(y,z))<0){rotate(x);break;}
116 if(d1==d2) rotate(y),rotate(x);
117 else rotate(x),rotate(x);
118 } x->update();return x;
119 }
120 void add(snode*x,snode*&y,info tag){
121 x->init();x->x=tag;x->ch[0]=y;if(y)y->fa=x;x->update();y=x;return;
122 }
123 void detach(node*x){
124 add(x->ch[1]->s[0]->id+Splay,root[x->id],x->ch[1]->all);return;
125 }
126 void connect(node*x,node*y){
127 snode*p=y->s[0]->id+Splay;splay(p);
128 if(p->ch[0]) p->ch[0]->fa=NULL;
129 if(p->ch[1]) p->ch[1]->fa=NULL;
130 root[x->id]=join(p->ch[0],p->ch[1]);
131 y->chat(p->all);y->tret(p->all);return;
132 }
133 node*access(node*x){
134 node*ret=NULL;
135 for(;x;x=x->fa){
136 if(splay(x)->ch[1]) detach(x);
137 if(x->ch[1]=ret) connect(x,ret);
138 (ret=x)->update();
139 } return ret;
140 }
141 void makeroot(int x){access(x+lct)->revt();return;}
142 void link(int x,int y){
143 access(lct+y);splay(lct+y)->ch[1]=lct+x;makeroot(x);splay(lct+x)->fa=lct+y;return;
144 }
145 node*findfa(node*x){
146 x=splay(x)->ch[0];
147 if(!x) return x;
148 else return x->s[1];
149 }
150 int queryfa(int x){
151 node*t;access(x+lct);
152 if(!(t=findfa(x+lct))) return -1;
153 else return t->x.sm;
154 }
155 int treeroot;
156 node*findtop(node*x){return splay(x)->s[0];}
157 bool insub(int x,int y){
158 if(x==y||x==treeroot) return true;
159 access(y+lct);if(findtop(x+lct)==findtop(y+lct)) return true;
160 return false;
161 }
162 void changesub(int x,int y,tag t){
163 makeroot(x);access(lct+y);splay(lct+y);
164 lct[y].x=lct[y].x+t;
165 if(root[y]) root[y]->addt(t);
166 lct[y].update();return;
167 }
168 void changecha(int x,int y,tag t){
169 makeroot(x);access(lct+y)->chat(t);return;
170 }
171 info querycha(int x,int y){
172 makeroot(x);return access(lct+y)->sm;
173 }
174 info querysub(int x,int y){
175 makeroot(x);access(lct+y);splay(lct+y);return root[y]?lct[y].x+root[y]->sm:lct[y].x;
176 }
177 void cutfa(int x){
178 node*t=(access(lct+x),splay(lct+x));
179 t->ch[0]=t->ch[0]->fa=NULL;t->update();return;
180 }
181 void linkfa(int x,int fa){
182 access(fa+lct);splay(lct+fa);makeroot(x);splay(lct+x)->fa=lct+fa;lct[fa].update();
183 add(Splay+x,root[fa],lct[x].all);
184 return;
185 }
186 void splitfa(int r,int x,int fa){
187 makeroot(r);if((access(lct+x),access(lct+fa))==lct+x) return;
188 cutfa(x);linkfa(x,fa);return;
189 }
190 int n,Q,p1[maxn],p2[maxn],A[maxn];
191 void inittree(int*a){
192 for(int i=1;i<=n;i++){
193 lct[i].id=i;
194 lct[i].s[0]=lct[i].s[1]=lct+i;
195 lct[i].x=lct[i].sm=lct[i].all=(info){a[i],a[i],1,a[i]};
196 lct[i].cha=lct[i].tre=nulltag;
197 } return;
198 }
199 inline int read(){
200 int x=0,sig=1;char ch=getchar();
201 while(!isdigit(ch)){if(ch=='-')sig=-1;ch=getchar();}
202 while(isdigit(ch))x=10*x+ch-'0',ch=getchar();
203 return x*=sig;
204 }
205 inline void write(long long x){
206 if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x;
207 int len=0;static long long buf[20];while(x)buf[len++]=x%10,x/=10;
208 for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return;
209 }
210 void init(){
211 n=read();Q=read();
212 for(int i=2;i<=n;i++) p1[i]=read(),p2[i]=read();
213 for(int i=1;i<=n;i++) A[i]=read();
214 inittree(A);
215 for(int i=2;i<=n;i++) link(p1[i],p2[i]);
216 treeroot=read();makeroot(treeroot);
217 return;
218 }
219 void work(){
220 int x,y,z,tp;
221 while(Q--){
222 tp=read();x=read();
223 switch(tp){
224 case 0:
225 makeroot(x),treeroot=x;
226 break;
227 case 1:
228 changecha(x,x,(tag){0,read()});
229 break;
230 case 2:
231 changecha(x,x,(tag){1,read()});
232 break;
233 case 3:
234 changecha(x,x,(tag){read(),0});
235 break;
236 case 4:
237 write(querycha(x,x).mi);ENT;
238 break;
239 case 5:
240 y=read();changecha(x,y,(tag){0,read()});
241 break;
242 case 6:
243 y=read();changecha(x,y,(tag){1,read()});
244 break;
245 case 7:
246 y=read();changecha(x,y,(tag){read(),0});
247 break;
248 case 8:
249 y=read();write(querycha(x,y).mi);ENT;
250 break;
251 case 9:
252 y=read();write(querycha(x,y).mx);ENT;
253 break;
254 case 10:
255 y=read();write(querycha(x,y).sm);ENT;
256 break;
257 case 11:
258 y=read();write(querycha(x,y).siz);ENT;
259 break;
260 case 12:
261 changesub(treeroot,x,(tag){0,read()});
262 break;
263 case 13:
264 changesub(treeroot,x,(tag){1,read()});
265 break;
266 case 14:
267 changesub(treeroot,x,(tag){read(),0});
268 break;
269 case 15:
270 write(querysub(treeroot,x).mi);ENT;
271 break;
272 case 16:
273 write(querysub(treeroot,x).mx);ENT;
274 break;
275 case 17:
276 write(querysub(treeroot,x).sm);ENT;
277 break;
278 case 18:
279 write(querysub(treeroot,x).siz);ENT;
280 break;
281 case 19:
282 y=read();splitfa(treeroot,x,y);
283 break;
284 case 20:
285 y=read();if(insub(x,y)) puts("true");else puts("false");
286 break;
287 case 21:
288 write(queryfa(x));ENT;
289 break;
290 }
291 }
292 return;
293 }
294 void print(){
295 return;
296 }
297 int main(){init();work();print();return 0;}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
