QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#127663 | #6745. Delete the Tree | jeffqi | AC ✓ | 1ms | 3612kb | C++23 | 1.7kb | 2023-07-19 21:43:04 | 2023-07-19 21:43:05 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define sz(v) ((int)v.size())
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define i128 __int128
using namespace std;
namespace qiqi {
void main() {
int n;
cin >> n;
vector<vi> e(n);
for (int i = 0; i < n-1; i++) {
int u,v;
cin >> u >> v; u--; v--;
e[u].eb(v); e[v].eb(u);
}
vi dep(n);
{
vi vis(n),siz(n),mx(n);
auto solve = [&](auto self,int u,int d) -> void {
vi vec;
auto dfs = [&](auto self,int u,int fa) -> void {
vec.eb(u); siz[u] = 1; mx[u] = 0;
for (auto v:e[u]) {
if (v != fa && !vis[v]) {
self(self,v,u);
siz[u] += siz[v];
mx[u] = max(mx[u],siz[v]);
}
}
};
dfs(dfs,u,-1);
int sum = siz[u];
u = *min_element(all(vec),[&](int i,int j) {
return max(mx[i],sum-siz[i]) < max(mx[j],sum-siz[j]);
});
vis[u] = 1; dep[u] = d;
for (auto v:e[u]) {
if (!vis[v]) {
self(self,v,d+1);
}
}
};
solve(solve,0,0);
}
int m = *max_element(all(dep))+1;
vector<vi> vec(m);
for (int i = 0; i < n; i++) {
vec[dep[i]].eb(i);
}
reverse(all(vec));
cout << m << '\n';
for (auto p:vec) {
cout << sz(p) << ' ';
for (auto x:p) {
cout << x+1 << ' ';
}
cout << '\n';
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
qiqi::main();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3504kb
input:
5 1 2 1 3 1 4 4 5
output:
3 1 5 3 2 3 4 1 1
result:
ok
Test #2:
score: 0
Accepted
time: 1ms
memory: 3552kb
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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...
result:
ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3568kb
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 3 5 7 8 10 15 18 20 21 23 27 28 32 33 34 35 43 46 48 50 51 53 54 55 56 61 62 63 64 65 68 72 76 77 78 79 83 86 87 88 89 91 93 94 95 96 98 106 109 111 114 118 120 123 125 126 127 128 130 131 135 137 138 139 143 144 146 147 149 150 151 152 154 156 158 159 161 162 164 165 167 168 171 172 174 177 1...
result:
ok
Test #4:
score: 0
Accepted
time: 1ms
memory: 3572kb
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 4 5 6 7 8 10 11 13 14 16 20 22 24 25 27 28 29 31 32 37 38 39 44 50 51 54 55 57 61 62 63 64 65 70 74 77 79 80 81 82 83 86 92 94 95 97 98 102 103 105 106 110 112 113 114 115 116 119 122 123 124 127 129 131 132 135 137 140 143 144 148 149 152 155 157 158 160 161 164 165 167 168 170 173 175 176 17...
result:
ok
Test #5:
score: 0
Accepted
time: 1ms
memory: 3496kb
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 1 85 252 3 5 6 7 9 10 18 19 20 22 24 25 27 29 31 32 33 34 35 37 38 39 41 44 47 48 49 51 53 57 58 59 60 61 62 63 64 66 67 70 71 73 81 86 87 90 91 94 95 96 100 107 112 113 116 120 123 128 129 132 133 138 139 140 141 142 143 147 149 153 155 156 158 160 161 163 164 166 168 169 170 173 174 180 181 182...
result:
ok
Test #6:
score: 0
Accepted
time: 1ms
memory: 3540kb
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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 70 71 72 74 75 76 77 78 79 80 81 83 84 85 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 10...
result:
ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3536kb
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 14 8 27 64 81 150 167 180 206 276 311 344 414 430 466 92 2 13 21 32 37 38 41 42 44 45 47 53 66 67 77 79 83 94 98 100 112 121 126 138 147 151 152 166 173 192 193 195 205 223 225 252 253 260 261 267 268 278 282 284 286 288 296 305 308 316 317 318 319 322 325 332 338 352 359 366 369 372 383 385 386 ...
result:
ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3612kb
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 41 12 27 38 40 47 57 76 84 89 106 131 142 143 145 162 199 201 206 213 251 255 261 264 272 274 295 296 305 327 332 335 338 347 356 370 417 418 419 424 431 481 105 3 23 29 30 34 35 36 49 51 56 58 61 65 67 74 82 86 87 92 110 112 113 116 120 137 138 139 148 150 152 157 158 163 166 169 174 185 189 209...
result:
ok
Test #9:
score: 0
Accepted
time: 1ms
memory: 3576kb
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 3 6 9 16 23 53 83 95 104 113 123 161 168 174 176 177 181 200 218 234 244 252 260 266 277 291 296 304 319 321 323 336 373 374 375 377 378 381 390 392 396 397 433 434 439 441 452 474 128 4 5 7 8 11 12 17 19 20 21 22 25 26 27 34 40 41 43 45 52 57 60 65 70 71 75 77 79 80 81 87 94 100 102 111 112 1...
result:
ok
Test #10:
score: 0
Accepted
time: 1ms
memory: 3608kb
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 2 4 6 8 10 13 14 16 22 25 28 32 35 38 42 44 45 48 50 55 56 60 61 65 67 68 76 78 80 82 90 91 93 94 99 100 103 104 108 109 110 113 115 117 118 121 122 123 127 128 134 136 138 141 142 143 149 152 153 154 156 159 161 162 163 164 165 168 169 170 173 174 178 179 182 189 198 201 202 204 205 206 207 2...
result:
ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3532kb
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 4 10 13 14 15 20 21 33 35 37 38 43 48 62 73 78 80 85 87 92 96 97 106 109 113 116 117 120 128 131 144 145 147 148 157 158 160 174 176 177 185 188 194 195 198 200 202 207 216 224 230 237 240 244 249 255 268 270 272 277 279 287 288 289 295 296 299 300 306 308 312 319 323 328 334 342 344 345 351 3...
result:
ok
Test #12:
score: 0
Accepted
time: 1ms
memory: 3540kb
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 5 6 18 37 57 73 78 85 93 98 101 102 120 130 140 142 148 163 173 174 199 219 238 245 254 259 292 297 303 309 325 331 334 338 344 348 352 354 355 359 363 368 392 408 409 423 439 453 458 472 484 492 184 1 2 7 16 20 21 22 24 25 33 40 43 45 46 47 49 52 54 56 61 62 64 65 70 72 74 75 79 81 82 84 88 9...
result:
ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3608kb
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 9 32 195 238 278 332 376 397 430 432 441 481 120 1 3 10 20 26 28 34 39 41 46 48 50 52 60 61 67 71 73 74 79 84 87 90 94 95 97 108 110 120 129 136 146 147 148 150 153 154 155 166 170 175 181 182 184 186 189 191 200 202 206 222 225 228 229 232 234 240 244 246 248 253 256 257 259 260 262 263 264 2...
result:
ok
Test #14:
score: 0
Accepted
time: 1ms
memory: 3600kb
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 39 48 61 68 72 87 127 139 154 192 203 213 219 232 237 240 274 280 295 304 321 338 349 385 392 398 431 448 452 486 132 4 5 9 20 41 42 43 47 51 56 57 58 59 62 66 69 75 77 82 84 102 103 113 118 125 128 133 140 146 148 149 159 162 163 164 166 170 184 185 187 195 211 214 216 218 224 226 230 235 239...
result:
ok
Test #15:
score: 0
Accepted
time: 1ms
memory: 3608kb
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 4 6 9 12 15 17 20 22 25 32 33 39 44 55 63 69 73 81 83 86 87 88 91 98 110 111 115 118 121 123 128 131 138 146 151 157 165 166 172 179 185 191 192 198 199 223 229 230 231 237 244 248 250 251 252 253 259 260 261 263 267 268 274 278 286 298 310 322 329 335 341 354 364 371 377 393 408 424 428 433 43...
result:
ok
Test #16:
score: 0
Accepted
time: 1ms
memory: 3496kb
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 25 26 30 37 49 133 191 204 215 245 274 314 349 406 421 426 450 451 460 152 1 3 4 5 6 11 19 20 21 23 32 33 43 48 51 53 58 59 61 62 64 65 66 68 70 82 83 87 90 92 93 95 96 102 103 104 105 107 109 110 113 117 120 122 125 135 136 140 149 150 159 164 167 169 173 186 190 192 193 195 196 206 207 211 2...
result:
ok
Test #17:
score: 0
Accepted
time: 1ms
memory: 3504kb
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 48 23 45 52 55 58 70 77 109 113 132 139 147 152 164 172 186 188 225 230 231 235 248 258 259 265 267 268 274 285 286 293 306 307 329 333 341 345 354 357 375 380 383 408 430 441 446 486 500 87 2 7 11 15 28 33 41 47 51 61 67 72 80 86 97 111 114 118 127 134 137 141 143 145 150 159 163 171 181 182 184...
result:
ok
Test #18:
score: 0
Accepted
time: 1ms
memory: 3516kb
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 147 1 2 3 5 6 12 15 16 19 23 24 26 31 33 36 38 39 46 53 54 58 60 67 69 70 71 72 73 80 86 91 93 96 97 104 113 114 116 118 120 126 128 129 133 140 143 153 155 158 164 166 173 179 185 186 187 192 207 208 213 217 227 233 238 239 240 243 244 247 248 249 250 251 252 259 261 264 266 269 277 286 289 292 2...
result:
ok
Test #19:
score: 0
Accepted
time: 1ms
memory: 3536kb
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 1 4 6 11 15 16 19 25 27 28 31 33 35 36 41 44 45 49 53 55 59 60 70 74 75 79 84 86 87 88 90 91 93 103 104 110 112 120 121 125 126 128 129 130 132 135 138 139 140 145 149 153 154 155 157 158 161 163 166 167 168 172 173 174 177 178 181 184 185 187 192 198 201 205 206 208 210 212 213 218 219 222 22...
result:
ok
Test #20:
score: 0
Accepted
time: 1ms
memory: 3500kb
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 2 9 13 14 24 25 28 29 33 48 50 52 53 54 55 56 57 59 60 61 63 65 66 68 72 73 79 86 88 90 92 93 94 96 107 108 110 118 119 121 122 124 129 130 131 132 133 136 150 151 152 162 171 178 180 187 188 190 204 206 208 218 223 229 230 232 237 239 240 246 247 250 257 258 262 273 275 280 283 287 290 291 30...
result:
ok
Test #21:
score: 0
Accepted
time: 1ms
memory: 3600kb
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 3 56 247 412 24 18 23 50 57 77 88 90 119 123 124 125 167 172 177 191 203 235 242 305 317 358 379 418 474 85 15 30 36 38 43 44 45 49 65 67 84 91 92 104 106 108 111 126 128 137 141 142 159 164 166 174 175 178 183 189 192 200 201 204 208 220 231 243 245 249 250 257 264 265 269 290 299 304 306 312 3...
result:
ok
Test #22:
score: 0
Accepted
time: 1ms
memory: 3572kb
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 171 337 401 49 1 19 27 33 39 57 58 65 79 94 125 147 151 176 198 225 227 252 254 257 266 270 272 274 278 280 282 305 311 314 331 336 358 359 366 380 381 390 398 400 412 416 417 430 469 472 474 475 490 108 3 7 10 21 22 34 36 38 44 47 51 52 53 67 71 76 83 85 88 89 97 98 104 105 108 114 123 124 13...
result:
ok
Test #23:
score: 0
Accepted
time: 1ms
memory: 3576kb
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 2 4 5 15 20 32 37 39 40 43 46 51 54 58 63 68 71 80 84 85 97 100 101 105 112 118 120 125 126 133 134 136 139 142 145 155 156 161 174 176 190 194 197 199 202 208 209 213 214 217 224 225 233 234 235 239 242 252 253 255 259 260 268 269 270 271 276 283 285 289 290 295 301 304 305 307 314 316 317 32...
result:
ok
Test #24:
score: 0
Accepted
time: 1ms
memory: 3500kb
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 9 13 22 25 27 36 45 59 75 81 84 85 86 108 109 119 122 129 143 149 160 171 175 181 189 190 191 206 210 215 216 224 225 244 252 254 255 267 273 276 289 307 316 317 320 328 339 340 342 351 353 354 362 366 368 371 375 382 393 395 402 414 418 419 426 427 431 448 449 450 454 463 469 471 472 473 478 4...
result:
ok