QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#413011 | #6745. Delete the Tree | Savior | AC ✓ | 1ms | 7832kb | C++20 | 1.3kb | 2024-05-16 23:47:01 | 2024-05-16 23:47:02 |
Judging History
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();
}
}
Details
Tip: Click on the bar to expand more detailed information
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