QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#412641 | #6745. Delete the Tree | Hirro | AC ✓ | 1ms | 3792kb | C++14 | 1.1kb | 2024-05-16 16:54:45 | 2024-05-16 16:54:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 1505;
vector<int> e[N];
vector<int>a;
int siz[N], root, mx = 1e9, del[N] = { 0 }, p = 0;
vector<int> ans[20];
void getroot(int u, int fa, int tot) {
siz[u] = 1;
int ms = 0;
for (auto& v : e[u]) {
if (v == fa || del[v])continue;
getroot(v, u, tot);
siz[u] += siz[v];
ms = max(ms, siz[v]);
}
ms = max(ms, tot - siz[u]);
if (ms < mx)root = u, mx = ms;
}
void dfs(int u, int fa,int m) {
p = max(p, m);
mx = 1e9;
getroot(u, 0, siz[u]);
u = root;
getroot(u, 0, siz[u]);
del[u] = 1;
ans[m].push_back(u);
for (auto& v : e[u]) {
if (del[v] || v == fa)continue;
dfs(v, 0, m + 1);
}
}
void solve() {
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
siz[1] = n;
dfs(1, 0, 0);
cout << p+1 << '\n';
for (int i = p; i >=0;i--) {
cout << ans[i].size() << ' ';
for (auto& v : ans[i])cout << v << ' ';
cout << '\n';
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
//int t;
//cin >> t;
//while (t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3684kb
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: 3700kb
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: 3792kb
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: 3772kb
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: 3652kb
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 4...
result:
ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3736kb
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: 3664kb
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 27...
result:
ok
Test #8:
score: 0
Accepted
time: 1ms
memory: 3656kb
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 20...
result:
ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3672kb
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 1...
result:
ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3656kb
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: 1ms
memory: 3732kb
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: 0ms
memory: 3656kb
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: 0ms
memory: 3708kb
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: 0ms
memory: 3720kb
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: 0ms
memory: 3664kb
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: 3792kb
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 1...
result:
ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 3760kb
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 46...
result:
ok
Test #18:
score: 0
Accepted
time: 1ms
memory: 3748kb
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: 0ms
memory: 3612kb
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: 3720kb
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: 3708kb
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 4...
result:
ok
Test #22:
score: 0
Accepted
time: 1ms
memory: 3656kb
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...
result:
ok
Test #23:
score: 0
Accepted
time: 0ms
memory: 3712kb
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: 3724kb
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