QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#184641#6745. Delete the Treebulijiojiodibuliduo#AC ✓1ms4208kbC++1.6kb2023-09-21 01:01:592023-09-21 01:01:59

Judging History

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

  • [2023-09-21 01:01:59]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:4208kb
  • [2023-09-21 01:01:59]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=1010;
int q[N],f[N],vis[N],sz[N],ms[N];
int n;
VI e[N];
int find(int u) {
	int t=1;q[0]=u;f[u]=-1;
	rep(i,0,t) {
		u=q[i];
		rep(j,0,e[u].size()) {
			int v=e[u][j];
			if (!vis[v]&&v!=f[u]) f[q[t++]=v]=u;
		}
		ms[q[i]]=0;
		sz[q[i]]=1;
	}
	for (int i=t-1;i>=0;i--) {
		ms[q[i]]=max(ms[q[i]],t-sz[q[i]]);
		if (ms[q[i]]*2<=t) return q[i];
		sz[f[q[i]]]+=sz[q[i]];
		ms[f[q[i]]]=max(ms[f[q[i]]],sz[q[i]]);
	}
	return 0;
}

vector<VI> ans;
void gao(int u,int lev) {
	u=find(u);
	if (SZ(ans)<=lev) ans.pb(VI());
	ans[lev].pb(u);
	vis[u]=1;
	for (auto v:e[u]) if (!vis[v]) gao(v,lev+1);
}

int main() {
	scanf("%d",&n);
	rep(i,1,n) {
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].pb(v);
		e[v].pb(u);
	}
	gao(1,0);
	printf("%d\n",SZ(ans));
	reverse(all(ans));
	for (auto x:ans) {
		printf("%d", SZ(x));
		for (auto y:x) printf(" %d",y);
		puts("");
	}
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 4164kb

input:

5
1 2
1 3
1 4
4 5

output:

3
1 4
3 2 3 5
1 1

result:

ok 

Test #2:

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

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 183 32 334 254 331 348 54 430 275 410 360 468 140 179 93 327 128 365 122 43 46 399 398 269 130 227 412 61 295 98 30 197 397 95 192 266 48 310 283 127 123 7 154 317 302 158 65 218 306 191 309 210 20 190 204 484 182 429 362 99 92 347 39 488 58 115 228 8 346 111 386 498 408 259 289 333 256 352 26...

result:

ok 

Test #3:

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

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 1 323 205 480 454 142 346 389 232 228 357 362 316 163 176 210 294 124 339 223 409 175 474 181 81 140 301 134 215 471 4 122 456 160 484 331 318 22 69 105 342 219 363 446 194 408 25 101 84 407 60 488 348 157 358 211 423 169 403 303 499 486 286 436 356 493 190 47 366 347 90 213 264 75 398 102 70 ...

result:

ok 

Test #4:

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

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 488 413 265 398 241 386 210 147 19 335 261 425 156 420 309 441 183 204 151 382 414 451 27 149 10 218 115 86 110 20 471 266 432 424 269 12 308 226 333 234 104 70 434 457 406 179 473 239 227 190 365 79 81 123 416 483 80 338 467 5 470 188 212 347 476 332 341 55 270 253 152 362 371 404 89 47 423 2...

result:

ok 

Test #5:

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

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
2 104 178
251 147 441 62 223 140 422 434 120 189 169 109 20 6 450 133 417 184 367 19 59 377 477 39 57 25 255 240 182 198 396 300 291 453 156 53 306 153 81 91 116 173 410 24 261 61 174 423 149 499 71 60 143 424 86 322 158 206 166 398 348 226 394 358 296 34 443 218 268 269 326 369 186 407 408 388 47...

result:

ok 

Test #6:

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

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 95 437 337 152 185 484 165 41 322 334 32 118 232 57 329 89 482 54 461 433 226 183 229 102 468 253 328 115 452 470 210 90 403 55 123 206 251 236 98 290 471 301 22 167 124 179 310 79 205 492 245 113 276 38 241 33 46 488 312 169 345 466 122 129 272 161 143 282 379 462 293 263 63 224 493 318 99 36...

result:

ok 

Test #7:

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

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:

9
12 374 385 98 267 307 13 121 64 476 386 305 347
97 463 344 371 414 206 43 429 366 225 401 308 276 27 444 268 83 422 252 415 77 80 147 367 122 184 317 286 359 311 81 8 466 174 405 180 331 418 38 32 79 213 329 377 103 146 273 128 200 378 472 471 39 85 372 42 408 465 426 260 376 482 270 277 2 412 278...

result:

ok 

Test #8:

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

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:

8
44 464 11 239 174 436 340 126 66 274 385 223 481 84 57 145 405 225 395 157 244 411 42 389 356 76 290 254 468 23 264 38 201 27 131 86 40 47 258 479 56 418 213 12 296
101 342 462 283 444 51 416 110 424 492 281 404 371 251 319 53 65 139 216 233 87 420 29 449 344 365 452 24 163 282 200 467 451 250 207...

result:

ok 

Test #9:

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

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 453 150 418 49 263 313 75 360 157 233 236 57 415 58 62 146 366 385 394 195 29 500 289 183 269 295 316 419 197 469 461 179 449 91 155 414 281 68 247 89 334 238 490 240 484 131 163 447
128 174 479 223 170 190 19 405 296 291 475 411 98 446 308 481 177 304 136 368 156 440 369 406 321 104 444 410 15...

result:

ok 

Test #10:

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

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:

8
192 366 44 472 317 388 61 350 426 4 138 122 319 223 207 398 128 104 165 494 328 382 222 416 227 136 325 161 254 221 100 443 467 252 268 320 121 260 247 490 163 6 284 208 164 282 304 393 99 173 28 241 332 314 115 78 327 235 392 367 16 313 110 364 68 182 156 300 204 315 198 90 374 352 153 93 285 395...

result:

ok 

Test #11:

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

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
119 264 480 88 65 438 34 191 364 490 23 411 494 4 300 423 308 348 297 206 199 253 325 216 147 342 120 76 321 6 50 24 385 298 401 381 67 422 160 131 295 317 69 201 182 75 484 27 57 388 134 269 450 476 454 455 177 425 20 488 200 145 279 48 188 403 345 174 435 37 413 39 286 213 447 386 328 10 440 319...

result:

ok 

Test #12:

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

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:

8
52 241 469 316 471 47 114 2 365 58 194 92 411 42 209 299 437 157 364 438 168 105 56 291 215 73 309 414 275 178 286 144 481 213 212 135 318 143 478 176 91 160 243 180 146 145 244 250 271 337 444 423 120
184 8 251 167 137 198 349 111 201 228 273 376 90 84 441 409 378 35 323 440 121 21 425 468 48 86 ...

result:

ok 

Test #13:

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

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
12 354 409 111 130 164 447 172 14 237 69 410 83
120 245 401 477 16 179 22 213 439 239 95 382 391 461 373 323 167 79 110 316 332 321 292 59 223 288 45 48 39 153 406 78 421 180 170 1 498 238 427 350 327 5 207 451 367 414 379 311 102 295 74 120 264 222 312 241 290 325 256 320 9 147 249 322 408 491 2 ...

result:

ok 

Test #14:

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

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:

8
30 119 341 152 277 434 96 425 115 495 204 323 358 93 363 329 428 136 164 351 405 128 331 272 433 441 125 301 404 452 232
132 245 81 31 15 174 209 194 296 150 149 166 133 230 161 126 97 401 170 292 240 57 79 435 320 456 158 378 308 75 382 157 376 270 491 418 27 192 488 187 380 430 67 220 101 51 41 ...

result:

ok 

Test #15:

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

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:

8
91 457 482 214 365 194 353 62 236 127 153 454 384 213 195 234 101 2 108 412 358 318 449 265 147 336 355 387 403 244 22 296 72 312 368 28 37 369 397 362 90 250 123 87 191 484 263 230 278 199 480 413 472 141 280 75 305 104 218 76 240 459 12 121 172 128 341 408 298 464 377 109 316 427 376 53 256 181 ...

result:

ok 

Test #16:

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

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
19 127 338 144 94 242 121 17 44 336 376 301 27 107 68 305 284 487 430 464
152 354 60 480 10 293 485 365 441 482 136 420 411 109 230 201 392 345 281 466 426 283 374 116 216 240 218 20 494 269 122 290 385 106 211 32 469 30 224 455 256 31 178 366 276 97 439 203 45 41 264 355 241 300 124 282 86 207 11...

result:

ok 

Test #17:

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

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
49 315 263 335 288 391 430 307 441 188 200 73 404 260 152 378 392 150 462 371 240 444 143 480 159 255 439 484 273 336 271 80 305 485 259 97 269 230 446 201 15 333 375 86 18 134 63 67 290 9
86 139 329 231 410 121 157 267 286 173 114 357 109 408 137 367 383 54 100 37 326 218 129 41 356 44 19 118 461...

result:

ok 

Test #18:

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

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:

9
176 328 140 2 381 244 101 7 478 346 458 280 436 8 74 428 300 321 182 93 6 418 251 388 176 313 270 228 361 40 100 277 81 99 151 177 416 357 58 286 311 46 80 38 342 338 385 429 279 51 314 122 345 35 184 409 161 21 196 426 246 37 214 169 470 202 290 134 363 448 150 351 331 105 4 482 348 451 266 129 4...

result:

ok 

Test #19:

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

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 165 85 409 153 68 88 264 319 258 78 209 196 124 141 23 459 412 332 144 34 402 193 146 433 431 61 197 400 408 118 182 95 326 345 3 421 32 485 324 179 123 298 143 446 331 108 5 107 227 329 349 51 207 117 29 176 82 2 159 445 477 99 189 253 285 286 76 311 302 57 489 96 92 270 498 171 299 242 343 2...

result:

ok 

Test #20:

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

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:

6
148 400 232 420 66 320 468 24 119 368 442 68 262 229 318 50 463 122 53 92 348 180 5 256 172 113 22 177 345 148 245 458 347 269 444 174 334 434 406 89 255 30 161 87 47 216 248 415 154 101 351 281 215 100 358 360 160 191 34 431 77 183 374 322 39 120 182 32 346 285 252 95 362 333 149 207 494 212 357 ...

result:

ok 

Test #21:

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

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:

8
5 417 250 201 269 245
22 388 157 254 321 320 325 188 197 437 67 176 317 125 334 88 305 418 247 192 312 365 288
87 287 378 38 423 18 280 420 485 346 94 440 182 37 65 130 44 468 299 290 23 137 31 244 447 177 203 242 119 412 56 128 141 231 343 273 213 405 257 477 431 90 164 159 167 387 77 104 111 459...

result:

ok 

Test #22:

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

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:

8
3 39 79 58
46 491 198 125 33 389 331 27 93 468 475 257 21 116 131 73 311 381 336 274 65 474 272 278 312 98 159 248 270 421 225 416 380 151 142 495 435 305 254 400 282 315 19 348 401 432 430
113 239 99 439 408 428 411 374 200 397 244 108 337 314 184 1 147 185 207 143 327 31 371 333 420 196 358 36 4...

result:

ok 

Test #23:

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

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 192 204 359 422 183 119 306 110 159 355 13 362 474 207 94 28 261 189 246 347 223 180 48 356 377 220 326 52 22 187 493 30 158 86 267 470 221 302 33 312 57 188 477 103 457 458 350 463 56 163 432 60 83 149 378 320 330 152 433 419 47 392 438 72 210 178 293 404 36 288 116 162 241 26 395 452 168 281...

result:

ok 

Test #24:

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

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 365 464 293 476 77 201 203 82 443 204 259 128 161 395 244 272 71 230 177 376 301 279 221 189 375 168 401 121 406 95 344 60 174 419 276 294 251 220 58 218 297 112 247 86 81 262 110 309 39 410 399 283 153 402 181 209 88 164 319 136 299 29 3 431 469 264 213 311 488 223 480 405 400 160 84 34 212 14...

result:

ok