QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#413011#6745. Delete the TreeSaviorAC ✓1ms7832kbC++201.3kb2024-05-16 23:47:012024-05-16 23:47:02

Judging History

你现在查看的是最新测评结果

  • [2024-05-16 23:47:02]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:7832kb
  • [2024-05-16 23:47:01]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N=1e6+5;
vector<int>ans[20];
int head[N],cntt;
struct Edge{
int to,next,val;
}edge[2*N];
void add(int u,int v,int x){
edge[++cntt].to=v;
edge[cntt].val=x;
edge[cntt].next=head[u];
head[u]=cntt;
}
int sum,vis[N],siz[N],maxp[N],rt;
void getrt(int x,int f){ //找重心
siz[x]=1;
maxp[x]=0;
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(vis[y]||y==f)continue;
getrt(y,x);
siz[x]+=siz[y];
if(siz[y]>maxp[x])maxp[x]=siz[y];
}
maxp[x]=max(maxp[x],sum-maxp[x]-1);
if(maxp[x]<maxp[rt])rt=x;
}
void dvd(int x,int dis){ //分治
vis[x]=1;
ans[dis].push_back(x);
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(vis[y])continue;
rt=0;
sum=siz[y];
getrt(y,y);
getrt(rt,rt);
dvd(rt,dis+1);
}
}
void solve(){
int n;
cin>>n;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
add(u,v,1);
add(v,u,1);
}
maxp[0]=sum=n;
getrt(1,1);
getrt(rt,rt);
dvd(rt,1);
int now=15;
while(ans[now].empty())now--;
cout<<now<<endl;
for(int i=now;i>=1;i--){
cout<<ans[i].size()<<' ';
for(auto j:ans[i])cout<<j<<' ';
cout<<endl;
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T=1;
// cin>>T;
while(T--){
solve();
}
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 7684kb

input:

5
1 2
1 3
1 4
4 5

output:

3
1 4 
3 5 3 2 
1 1 

result:

ok 

Test #2:

score: 0
Accepted
time: 0ms
memory: 7756kb

input:

500
183 443
32 443
334 443
254 443
331 443
348 443
54 443
430 443
275 443
410 443
360 443
443 468
140 443
179 443
93 443
327 443
128 443
365 443
122 443
43 443
46 443
399 443
398 443
269 443
130 443
227 443
412 443
61 443
295 443
98 443
30 443
197 443
397 443
95 443
192 443
266 443
48 443
310 443
28...

output:

2
499 55 126 471 14 209 482 253 372 63 473 411 385 36 188 407 432 247 457 361 376 414 394 5 178 467 451 107 370 374 97 66 196 96 225 229 187 456 45 27 270 166 250 217 287 431 56 231 234 249 291 81 71 282 181 465 434 427 200 148 70 379 146 9 426 343 279 458 393 267 452 147 340 113 369 417 62 232 415 ...

result:

ok 

Test #3:

score: 0
Accepted
time: 0ms
memory: 7684kb

input:

500
80 180
80 254
1 180
80 337
180 323
80 248
180 205
80 189
180 480
80 330
180 454
80 498
142 180
80 193
180 346
80 89
180 389
80 125
180 232
80 93
180 228
80 327
180 357
80 417
180 362
80 278
180 316
80 312
163 180
80 310
176 180
80 463
180 210
80 478
180 294
80 185
124 180
80 143
180 339
80 253
1...

output:

3
249 227 62 263 437 274 138 171 230 128 492 447 383 27 482 161 435 87 393 220 375 271 459 32 96 206 360 305 500 457 361 289 487 188 287 315 395 426 451 208 18 212 184 76 204 367 335 396 295 139 54 281 246 88 21 411 438 399 261 214 373 282 15 306 384 123 439 28 199 401 402 241 276 120 196 275 135 24...

result:

ok 

Test #4:

score: 0
Accepted
time: 1ms
memory: 7712kb

input:

500
387 488
301 488
301 413
13 413
13 265
176 265
176 398
74 398
74 241
241 415
386 415
386 448
210 448
210 285
147 285
147 264
19 264
19 314
314 335
54 335
54 261
261 484
425 484
350 425
156 350
156 164
164 420
8 420
8 309
230 309
230 441
408 441
183 408
183 410
204 410
204 318
151 318
151 328
328 ...

output:

9
245 455 233 221 69 15 256 162 288 411 73 351 154 255 163 26 356 40 259 52 286 320 92 137 458 294 390 160 155 437 375 496 305 215 251 203 1 355 71 459 418 303 97 446 157 102 325 277 450 399 388 345 200 100 395 427 369 379 68 360 429 243 254 141 118 43 307 487 422 87 171 300 247 268 460 24 442 385 2...

result:

ok 

Test #5:

score: 0
Accepted
time: 1ms
memory: 7832kb

input:

500
147 209
104 147
13 209
209 466
104 485
17 104
13 214
13 179
151 466
176 466
130 485
286 485
17 359
17 178
214 486
55 214
179 350
179 327
151 167
151 498
146 176
102 176
99 130
130 232
286 294
286 389
56 359
330 359
178 488
178 441
440 486
210 486
55 157
55 458
237 350
350 352
327 371
317 327
167...

output:

9
240 240 255 25 57 39 477 377 59 19 367 184 417 133 450 6 20 398 166 206 158 322 86 424 143 60 71 499 149 423 174 61 261 24 410 173 116 91 81 153 306 53 156 453 291 300 396 198 182 363 27 311 266 376 337 132 331 164 10 473 342 448 128 287 63 100 271 465 96 9 292 288 320 220 449 436 351 141 298 490 ...

result:

ok 

Test #6:

score: 0
Accepted
time: 1ms
memory: 7748kb

input:

500
323 449
449 474
198 449
431 449
69 449
336 449
402 449
240 449
43 449
82 449
335 449
86 449
427 449
220 449
26 449
449 477
449 465
73 449
325 449
1 449
144 449
432 449
203 449
443 449
95 323
323 437
323 337
152 323
185 323
323 484
165 323
41 323
322 323
323 334
32 323
118 323
232 323
57 323
323 ...

output:

3
475 413 52 74 112 373 181 146 109 438 151 499 195 298 111 348 106 294 453 422 397 417 267 344 156 170 332 94 490 235 440 27 168 364 304 231 426 228 281 360 20 354 133 207 163 307 393 5 173 349 8 418 455 378 450 387 196 243 42 362 448 186 446 374 76 242 368 247 271 188 149 246 353 158 237 454 100 4...

result:

ok 

Test #7:

score: 0
Accepted
time: 1ms
memory: 7760kb

input:

500
274 432
133 274
274 491
274 455
207 274
274 315
265 274
10 274
203 274
274 289
274 474
374 432
414 432
116 274
385 414
274 364
1 491
10 365
432 493
10 306
374 463
5 116
302 385
265 285
127 315
86 127
127 246
282 374
98 302
98 206
282 344
127 391
127 231
62 231
33 231
86 104
211 365
194 206
194 4...

output:

10
4 431 59 342 471 
73 199 288 53 12 425 272 17 198 60 245 438 49 93 420 457 84 90 490 229 20 208 354 292 65 400 214 166 399 340 152 160 107 94 341 343 388 392 227 278 412 7 45 319 353 85 331 386 169 178 444 308 194 302 325 177 451 368 125 361 441 360 240 387 165 473 110 128 273 146 103 377 329 213...

result:

ok 

Test #8:

score: 0
Accepted
time: 0ms
memory: 7812kb

input:

500
50 287
287 496
64 287
287 454
149 287
63 287
287 372
108 287
52 287
287 320
287 406
155 287
287 294
128 287
17 287
259 287
6 287
54 294
128 462
247 287
161 287
128 440
172 287
171 287
156 287
397 496
108 270
350 397
287 432
7 259
54 183
280 320
473 496
50 88
432 494
54 195
79 287
50 94
41 320
70...

output:

9
10 264 458 390 8 77 223 385 249 463 222 
66 296 12 213 418 56 479 258 47 40 86 427 131 27 201 297 370 23 468 254 290 456 279 423 21 14 428 4 238 49 33 42 411 60 20 374 157 395 225 405 61 89 138 378 265 295 193 66 67 369 137 242 113 339 275 83 386 313 206 126 227 78 205 449 239 11 464 
104 74 476 3...

result:

ok 

Test #9:

score: 0
Accepted
time: 1ms
memory: 7720kb

input:

500
93 209
209 367
209 438
209 314
209 332
152 209
209 443
209 471
209 315
209 342
209 459
209 460
209 462
209 211
209 341
191 209
209 329
185 209
209 350
209 468
209 493
209 363
209 224
35 209
209 253
209 212
86 209
204 209
186 209
209 262
193 209
209 275
209 427
141 209
88 209
149 209
209 409
209 ...

output:

9
48 447 163 131 484 240 490 238 334 89 247 68 281 414 155 91 449 179 461 469 197 419 316 295 269 183 289 500 29 195 394 385 366 146 62 58 415 57 236 233 157 360 75 313 263 49 418 150 453 
128 53 270 299 403 312 412 71 3 373 87 43 125 165 494 48 397 374 151 245 12 401 335 52 218 439 283 371 207 80 1...

result:

ok 

Test #10:

score: 0
Accepted
time: 1ms
memory: 7760kb

input:

500
130 139
139 400
130 318
267 318
318 389
21 400
21 36
21 26
267 321
321 401
18 321
200 389
200 307
66 200
36 274
95 274
96 274
26 357
192 357
220 357
385 401
290 385
46 385
18 53
53 301
53 231
166 307
166 287
3 166
66 212
212 410
212 438
95 155
151 155
155 305
41 96
41 478
41 148
112 192
112 137
...

output:

9
119 127 485 113 189 152 432 82 415 449 329 408 323 214 202 272 14 117 45 473 261 308 91 480 394 50 48 255 451 345 245 371 348 435 80 205 450 174 326 470 38 179 452 76 108 331 296 479 264 256 67 94 270 237 488 109 373 154 390 55 13 206 134 2 279 420 454 215 417 201 434 168 240 10 257 8 169 142 162 ...

result:

ok 

Test #11:

score: 0
Accepted
time: 1ms
memory: 7716kb

input:

500
117 264
117 456
175 264
264 500
2 456
218 456
175 480
175 343
265 500
432 500
2 475
2 487
63 218
218 421
377 480
444 480
84 343
151 343
265 281
133 265
252 432
181 432
346 475
445 475
16 487
330 487
25 63
63 102
79 421
101 421
266 377
142 377
409 444
434 444
84 291
84 284
8 151
151 333
281 358
2...

output:

9
237 496 129 121 220 41 307 313 77 340 54 296 344 85 458 410 361 464 354 33 446 127 146 416 115 136 118 152 276 415 239 499 141 30 311 187 47 240 87 202 198 7 406 369 404 229 238 386 447 213 286 39 413 37 435 174 345 403 188 48 279 489 145 95 375 261 247 149 256 472 68 384 272 78 442 249 80 396 195...

result:

ok 

Test #12:

score: 0
Accepted
time: 1ms
memory: 7684kb

input:

500
33 453
291 377
33 291
73 424
215 392
66 496
66 215
309 424
66 309
246 291
246 309
154 467
454 482
110 184
110 454
154 455
110 455
56 199
155 494
56 155
294 311
102 109
105 225
105 109
289 311
105 289
155 452
289 452
347 455
347 452
113 246
113 347
43 463
232 292
83 386
83 232
299 463
83 299
293 ...

output:

9
8 211 214 206 147 487 305 419 171 
86 473 420 461 249 380 162 160 65 82 428 216 27 80 186 177 265 145 146 120 423 444 337 271 250 278 131 220 23 296 321 379 478 143 480 357 279 464 144 286 227 202 3 284 181 293 272 195 336 282 299 43 232 115 252 185 60 221 247 319 438 364 309 73 215 291 56 105 127...

result:

ok 

Test #13:

score: 0
Accepted
time: 1ms
memory: 7736kb

input:

500
206 498
238 388
130 427
130 388
473 498
130 473
343 352
362 421
343 421
76 170
3 180
162 460
162 180
1 76
1 162
193 421
1 193
350 473
193 350
223 488
24 30
30 223
82 300
303 468
59 125
59 468
68 82
59 68
30 107
68 107
334 406
153 278
217 372
153 217
111 334
111 217
41 190
63 288
190 288
48 230
1...

output:

8
30 43 330 35 361 151 44 83 100 342 497 267 134 242 470 280 285 14 360 313 128 68 300 468 30 190 183 130 400 96 366 
135 247 415 224 54 148 80 436 49 70 181 221 410 378 499 335 195 131 248 434 19 370 309 496 38 204 418 194 140 363 244 479 441 104 333 225 254 297 121 25 21 47 275 450 341 57 324 46 1...

result:

ok 

Test #14:

score: 0
Accepted
time: 1ms
memory: 7756kb

input:

500
27 364
192 250
277 488
250 277
27 78
78 277
309 500
361 376
376 500
311 491
270 273
289 496
270 496
311 418
418 496
107 376
107 418
78 187
107 187
146 320
92 241
241 320
137 450
357 478
37 435
357 435
137 247
247 435
241 443
247 443
382 387
75 398
116 465
75 116
152 387
116 152
50 437
22 456
50 ...

output:

9
10 247 450 357 241 50 202 277 449 253 248 
56 137 478 37 92 146 350 437 22 24 184 261 152 382 75 488 192 27 418 491 270 376 462 214 3 458 5 99 446 9 399 211 213 156 166 149 150 296 194 209 151 52 243 472 81 245 53 143 312 302 191 172 96 319 285 231 222 
112 266 435 320 456 158 378 387 398 465 187 ...

result:

ok 

Test #15:

score: 0
Accepted
time: 0ms
memory: 7744kb

input:

500
224 468
4 105
342 365
105 365
133 224
133 365
293 476
176 389
389 476
162 227
41 411
453 489
411 453
36 162
36 453
297 389
36 297
133 485
297 485
23 486
95 136
136 486
158 314
10 65
302 491
65 491
314 495
491 495
54 136
54 495
169 488
91 483
40 68
40 483
214 488
40 214
186 375
372 465
186 465
59...

output:

9
71 386 383 500 18 187 409 144 243 414 359 66 423 492 420 181 256 53 376 427 316 109 377 464 298 408 341 128 172 121 12 459 240 76 218 104 305 75 280 141 472 413 480 199 278 230 263 484 191 87 123 250 90 362 397 369 37 28 368 312 72 296 495 158 65 136 186 418 365 233 239 27 
88 335 32 364 393 81 17...

result:

ok 

Test #16:

score: 0
Accepted
time: 0ms
memory: 7680kb

input:

500
289 469
30 302
94 224
94 302
175 469
94 175
363 495
38 385
385 495
211 433
106 239
202 268
106 202
32 433
32 202
114 385
32 114
175 455
114 455
92 216
14 459
216 459
262 299
63 321
116 228
63 116
111 299
111 116
324 459
111 324
122 165
269 274
15 193
15 269
144 165
15 144
65 360
77 240
240 360
2...

output:

8
37 464 430 487 284 305 68 107 72 36 156 198 292 317 27 9 381 448 500 145 481 143 351 273 44 209 47 56 111 262 63 459 360 331 94 142 219 254 
167 133 160 152 471 200 367 341 236 99 498 1 457 91 43 104 357 55 454 429 415 333 362 4 23 37 490 435 233 272 308 461 460 238 64 424 158 369 208 167 323 123 ...

result:

ok 

Test #17:

score: 0
Accepted
time: 0ms
memory: 7764kb

input:

500
139 315
285 315
263 285
263 329
329 335
132 335
132 288
231 288
231 391
266 391
266 430
410 430
307 410
307 379
117 379
117 121
121 441
370 441
188 370
157 188
157 200
200 486
73 486
73 267
267 404
32 404
32 260
260 286
286 296
296 499
350 499
173 350
152 173
152 458
378 458
114 378
114 172
172 ...

output:

9
63 9 467 47 498 442 229 11 2 246 184 185 490 99 317 437 7 279 181 77 58 354 225 338 182 164 127 420 293 259 485 305 80 271 336 402 484 439 72 203 455 159 480 143 54 240 371 462 150 392 378 152 32 267 486 188 441 307 430 391 288 335 263 315 
88 368 138 20 450 431 337 102 66 292 474 234 277 52 217 5...

result:

ok 

Test #18:

score: 0
Accepted
time: 1ms
memory: 7764kb

input:

500
315 328
140 315
140 285
2 285
2 455
381 455
381 391
244 391
172 244
101 172
101 479
7 479
7 456
456 478
372 478
300 372
300 471
321 471
321 413
182 413
182 209
93 209
93 359
6 359
6 500
418 500
276 418
251 276
251 291
291 388
388 400
288 400
277 288
123 277
81 123
81 165
164 165
99 164
99 406
15...

output:

10
5 10 446 327 30 167 
230 179 45 264 460 91 307 11 335 148 417 256 329 198 89 57 232 18 380 111 384 107 432 125 22 272 268 52 267 258 234 43 117 395 411 257 263 493 84 34 486 271 445 466 121 453 160 377 390 144 136 487 78 443 50 350 48 83 393 145 415 423 358 235 302 203 95 90 65 189 410 259 386 17...

result:

ok 

Test #19:

score: 0
Accepted
time: 1ms
memory: 7756kb

input:

500
87 420
87 165
165 457
85 457
85 187
187 435
56 435
56 409
268 409
153 268
40 153
40 225
225 451
68 451
68 362
88 362
88 190
190 397
122 397
122 264
202 264
75 202
304 420
304 319
200 319
200 258
258 318
24 318
24 138
78 138
78 357
209 357
209 497
58 497
16 58
16 196
196 488
124 488
124 155
155 4...

output:

6
169 490 20 414 131 48 388 54 260 294 195 353 354 391 169 275 481 315 127 308 119 406 22 211 466 151 274 80 150 347 220 66 487 133 389 379 191 479 255 458 450 300 237 266 356 410 180 384 418 371 12 322 355 64 114 448 262 483 101 434 427 271 440 424 366 98 306 276 426 293 273 338 14 113 385 50 336 3...

result:

ok 

Test #20:

score: 0
Accepted
time: 1ms
memory: 7768kb

input:

500
294 400
232 294
294 420
66 294
294 320
294 468
24 294
119 294
294 368
294 442
68 294
262 294
229 294
294 318
50 294
294 463
122 294
53 294
92 294
294 348
180 294
294 496
353 496
488 496
45 496
46 496
35 496
308 496
219 496
377 496
277 496
15 496
16 496
381 496
217 496
372 496
302 496
31 496
117 ...

output:

7
17 208 59 497 428 314 430 453 403 354 63 478 239 433 204 247 412 258 
132 7 23 411 319 490 489 176 295 419 454 209 272 104 201 179 91 410 471 235 339 276 159 397 156 170 202 482 465 307 379 450 163 357 212 494 207 149 333 362 95 252 285 346 32 182 43 470 317 329 337 495 236 10 380 499 70 448 487 4...

result:

ok 

Test #21:

score: 0
Accepted
time: 1ms
memory: 7688kb

input:

500
145 194
145 452
145 474
145 413
149 452
194 221
145 438
193 452
221 268
85 145
145 456
145 403
432 456
438 478
298 474
115 298
149 326
79 194
112 145
156 403
403 422
115 347
221 388
145 401
435 478
67 298
39 156
39 253
433 435
115 324
85 256
309 433
281 401
193 445
67 494
1 324
324 473
132 145
1...

output:

9
3 192 479 454 
19 245 459 111 104 77 334 129 39 472 200 395 337 2 152 487 100 398 276 280 
80 236 73 356 15 175 108 247 418 8 344 355 304 377 305 88 90 431 477 257 405 213 273 343 231 141 128 125 317 386 53 409 338 173 470 47 457 253 83 316 263 404 190 288 82 181 154 198 33 375 93 370 183 358 124 ...

result:

ok 

Test #22:

score: 0
Accepted
time: 1ms
memory: 7680kb

input:

500
206 289
289 478
239 289
212 289
212 326
173 206
262 289
24 262
239 250
289 456
326 465
35 478
465 491
215 289
124 215
215 288
8 288
157 289
289 342
116 326
326 453
206 422
236 465
116 292
325 465
2 124
326 448
188 448
132 326
69 478
133 239
8 42
24 127
28 116
135 342
262 473
115 325
126 206
268 ...

output:

9
5 58 164 392 172 258 
21 450 39 323 57 412 401 348 19 315 282 400 254 305 351 388 261 296 469 370 222 55 
79 248 159 98 312 274 336 381 311 278 272 474 65 44 73 53 292 21 257 475 468 93 331 79 337 314 33 125 198 491 141 498 394 71 181 228 451 418 430 497 88 295 85 308 306 417 7 34 51 350 209 481 2...

result:

ok 

Test #23:

score: 0
Accepted
time: 0ms
memory: 7692kb

input:

500
11 250
11 273
11 192
192 360
192 426
34 426
204 426
161 204
204 413
24 413
359 413
290 359
359 386
335 386
386 422
101 422
108 422
108 171
108 183
183 304
183 313
313 497
119 313
119 202
119 370
311 370
306 370
260 306
61 306
61 439
61 110
110 367
110 256
237 256
159 256
159 208
62 159
62 177
62...

output:

9
122 371 278 478 243 286 391 49 374 402 399 412 467 29 375 443 9 206 7 77 328 211 447 460 483 376 79 481 486 91 473 150 74 170 121 308 164 297 338 244 167 296 484 148 92 143 403 287 109 75 115 444 372 238 205 354 10 449 366 117 53 42 113 73 472 96 368 322 169 349 490 18 128 411 329 348 309 319 114 ...

result:

ok 

Test #24:

score: 0
Accepted
time: 1ms
memory: 7776kb

input:

500
365 463
365 477
324 477
310 477
106 477
106 232
41 106
106 125
125 464
125 293
125 467
467 478
190 467
6 467
6 141
6 453
6 435
412 435
435 444
435 484
476 484
77 484
421 484
156 421
360 421
182 421
182 273
182 471
182 315
115 315
56 315
179 315
179 320
179 328
179 499
242 499
390 499
436 499
201...

output:

9
79 418 368 210 108 366 267 84 160 129 206 85 342 469 431 317 25 225 254 175 351 255 454 362 36 22 45 181 402 252 448 414 224 81 86 191 382 473 449 109 354 216 353 393 316 27 307 276 419 426 495 59 171 375 189 450 75 496 472 427 9 122 215 143 13 371 149 244 395 289 339 119 340 328 320 471 273 190 4...

result:

ok