QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#387256 | #6745. Delete the Tree | Lackofgod | AC ✓ | 1ms | 3948kb | C++14 | 2.1kb | 2024-04-12 11:09:34 | 2024-04-12 11:09:34 |
Judging History
answer
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <map>
#include <bitset>
#include <stack>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <queue>
#define forn(i,aa,bb) for(int i=aa;i<=bb;++i)
#define LL long long
using namespace std;
const int N=500+5;
const LL mod=998244353;
const int MAXX=1e9;
int n;
vector<int> ed[N];
int sub[N];
int fa[N];
bool vis[N];
vector<int> ed1[N];
queue<int> q;
bool vis1[N];
void dfs1(int x){
vis[x]=1;
sub[x]=1;
for(int y:ed[x]) {
if (vis[y] || vis1[y]) continue;
fa[y]=x;
dfs1(y);
sub[x]+=sub[y];
}
}
int minm;
void dfs(int x,int &id,int sum){
sub[x]=1;
int maxm=0;
for(int y:ed[x]) {
if (y==fa[x] || vis1[y]) continue;
fa[y]=x;
dfs(y,id,sum);
sub[x]+=sub[y];
maxm=max(maxm,sub[y]);
}
maxm=max(maxm,sum-sub[x]);
if (maxm<=minm) minm=maxm,id=x;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
//cin>>T;
T=1;
while (T--) {
cin>>n;
forn(i,1,n-1) {
int x,y;
cin>>x>>y;
ed[x].push_back(y);
ed[y].push_back(x);
}
int root,num=0;
q.push(1);
sub[1]=n;
while (!q.empty()) {
int cnt=q.size();
num++;
while (cnt) {
minm=MAXX;
int k=q.front(); q.pop();
dfs(k,root,sub[k]);
dfs1(root);
ed1[num].push_back(root);
vis1[root]=1;
for(int y:ed[root]) {
if (vis1[y]) continue;
q.push(y);
}
cnt--;
}
forn(i,1,n)
vis[i]=0;
}
cout<<num<<'\n';
for(int i=num;i>=1;--i) {
cout<<ed1[i].size()<<' ';
for(int x:ed1[i])
cout<<x<<' ';
cout<<'\n';
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3908kb
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: 0ms
memory: 3864kb
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: 3696kb
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 254 337 248 189 330 498 193 89 125 93 327 417 278 312 310 463 478 185 143 253 272 277 91 404 53 68 64 424 78 458 72 5 177 156 218 48 433 137 256 245 329 333 146 131 391 94 237 413 406 65 431 441 233 377 168 118 242 298 259 285 35 63 336 344 260 483 494 465 428 386 313 186 109 414 79 191 440 34...
result:
ok
Test #4:
score: 0
Accepted
time: 1ms
memory: 3740kb
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 387 301 13 176 74 415 448 285 264 314 54 484 350 164 8 230 408 410 318 328 494 451 27 149 10 218 115 86 110 20 293 95 213 206 32 447 168 396 482 98 231 70 434 457 406 179 473 239 227 190 365 79 81 123 416 483 80 338 467 5 470 22 188 212 347 476 332 341 55 270 253 152 364 346 331 440 148 449 32...
result:
ok
Test #5:
score: 0
Accepted
time: 1ms
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 1 85 252 147 314 211 199 434 120 189 169 62 223 140 422 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: 3632kb
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: 0ms
memory: 3708kb
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 344 414 206 167 150 430 276 27 64 311 81 8 466 180 92 463 282 385 98 173 267 338 366 225 401 308 13 121 112 268 83 422 252 415 77 67 147 318 369 284 317 286 359 332 386 305 437 405 261 223 418 38 32 79 126 416 477 151 37 193 352 100 424 325 456 372 42 408 465 426 260 21 205 44 319 45 2 412 278...
result:
ok
Test #8:
score: 0
Accepted
time: 1ms
memory: 3640kb
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 424 251 305 142 143 347 206 274 295 89 481 84 57 145 419 327 261 431 332 417 370 356 76 199 272 106 264 38 201 27 131 162 255 40 47 338 335 418 213 12 296 105 58 82 380 440 51 416 447 110 492 281 404 371 485 259 239 65 139 216 233 87 29 209 449 112 344 174 452 92 309 163 282 483 245 150 345 48...
result:
ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3604kb
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 174 181 296 291 113 177 304 200 321 104 319 381 375 266 392 260 6 23 336 323 16 378 277 168 83 234 244 474 433 9 441 377 95 252 176 123 390 396 439 218 161 374 397 452 373 3 434 53 128 478 41 453 170 94 19 405 5 293 475 411 237 446 313 473 464 235 166 75 156 489 369 406 45 26 444 410 428 111 5...
result:
ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3928kb
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: 3948kb
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 117 377 463 176 15 255 73 439 97 287 14 237 4 300 423 308 148 35 460 390 43 389 216 147 342 120 157 116 368 128 113 21 395 62 144 289 422 160 131 295 483 334 353 195 396 80 249 442 78 272 450 476 454 455 177 425 20 488 200 145 489 279 48 188 403 345 174 435 37 413 268 158 288 194 277 328 10 44...
result:
ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3636kb
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 472 409 219 6 334 57 352 174 93 303 78 359 368 163 292 484 18 148 338 259 102 199 453 392 73 309 142 238 458 439 101 140 130 325 492 85 331 297 344 37 355 348 173 363 354 245 408 98 254 5 423 120 184 138 315 422 343 198 349 201 268 111 119 499 90 84 266 378 125 169 385 476 121 21 468 415 425 1...
result:
ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3928kb
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 376 332 278 238 397 9 32 430 441 481 432 195 120 87 240 229 26 150 399 457 20 228 95 382 461 403 391 232 353 79 110 90 321 463 182 303 488 41 10 48 39 406 372 153 352 3 170 1 206 427 388 350 327 34 304 344 84 260 369 454 337 383 74 120 222 191 264 305 146 325 256 420 147 284 97 46 442 52 404 2...
result:
ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3692kb
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 213 240 398 192 139 349 385 392 127 431 39 295 486 338 48 87 237 304 274 72 61 203 280 154 68 321 448 219 452 232 132 4 265 317 216 20 460 300 353 195 149 166 230 211 133 214 5 401 170 9 57 399 420 478 146 437 184 378 308 382 465 75 309 273 491 418 364 488 250 187 380 306 347 485 419 51 41 47 ...
result:
ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3700kb
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 192 44 91 4 165 433 466 424 442 15 20 253 223 166 115 157 138 179 268 260 267 231 329 259 98 456 25 274 244 22 470 185 55 371 73 39 83 33 63 198 250 123 87 191 484 263 230 278 199 480 322 286 428 252 354 251 6 131 146 462 151 12 121 172 128 341 408 298 464 377 248 86 237 474 229 118 261 310 110...
result:
ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 3692kb
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 204 426 274 30 215 191 421 450 349 49 451 406 460 37 245 25 26 314 133 152 103 322 105 445 337 164 19 443 169 136 420 109 335 411 135 364 345 281 332 283 425 195 321 92 65 410 20 494 122 193 269 363 239 211 32 289 224 302 455 256 186 387 265 456 368 312 21 248 263 264 355 300 93 241 491 353 20...
result:
ok
Test #17:
score: 0
Accepted
time: 1ms
memory: 3652kb
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 139 285 329 132 231 430 307 441 188 486 267 286 152 172 357 109 408 345 383 380 70 248 265 147 23 258 274 55 186 341 235 259 268 45 293 230 446 164 113 333 375 225 354 58 77 306 52 500 87 315 335 391 410 370 200 404 260 458 114 150 462 421 137 240 444 111 256 143 405 480 218 222 41 434 319 395...
result:
ok
Test #18:
score: 0
Accepted
time: 1ms
memory: 3940kb
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 328 140 2 381 244 479 456 404 376 54 67 294 389 72 26 471 413 93 6 251 299 433 442 495 31 207 318 360 277 164 406 312 416 357 58 286 311 46 80 38 342 385 354 39 366 289 240 492 474 379 16 133 371 86 394 323 303 71 166 60 482 348 451 266 129 475 185 155 36 462 444 116 301 158 114 118 186 187 36...
result:
ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 3588kb
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 87 187 153 225 88 397 75 304 318 138 497 16 155 130 462 247 370 208 288 1 383 350 41 125 184 185 310 351 223 238 325 112 11 19 110 168 438 15 173 399 212 330 60 382 374 320 476 442 206 352 33 428 241 272 250 334 296 104 444 25 471 232 192 157 219 359 53 55 90 93 468 463 86 441 6 301 396 423 10...
result:
ok
Test #20:
score: 0
Accepted
time: 0ms
memory: 3936kb
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 132 237 371 121 429 2 424 364 451 28 355 188 438 57 14 485 54 328 96 384 162 426 131 287 369 88 462 190 136 72 107 479 393 341 464 124 301 417 61 65 52 56 240 48 291 60 373 93 133 283 257 280 304 386 275 108 422 327 ...
result:
ok
Test #21:
score: 0
Accepted
time: 0ms
memory: 3732kb
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 412 56 247 24 18 474 235 172 23 191 123 177 203 242 119 317 125 50 379 90 88 305 418 167 77 124 358 57 85 43 378 38 423 265 497 36 402 361 67 429 49 447 92 243 264 142 137 65 290 357 341 44 468 299 417 250 201 269 128 141 231 343 45 390 257 477 431 362 164 159 245 387 192 104 111 304 108 175 1...
result:
ok
Test #22:
score: 0
Accepted
time: 0ms
memory: 3636kb
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 337 171 401 49 472 125 33 39 198 27 314 79 331 1 147 475 257 358 266 366 398 65 474 272 278 311 381 336 274 490 94 176 227 270 225 390 416 380 151 252 280 469 305 254 400 282 359 417 58 19 412 57 430 108 457 133 399 104 76 476 244 397 450 108 184 377 468 185 207 143 327 67 371 333 420 196 21 3...
result:
ok
Test #23:
score: 0
Accepted
time: 0ms
memory: 3904kb
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 360 161 290 101 304 202 260 367 208 325 85 63 340 285 436 4 408 84 345 488 156 489 405 283 357 259 424 190 43 214 317 125 459 321 301 199 15 269 380 58 314 406 416 352 253 342 252 420 276 400 217 499 289 145 242 351 71 134 2 97 268 343 54 383 136 233 40 334 271 307 39 363 461 462 126 155 197 4...
result:
ok
Test #24:
score: 0
Accepted
time: 0ms
memory: 3696kb
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 463 478 190 273 471 320 328 340 119 339 289 395 244 149 371 13 143 215 122 9 427 472 496 75 450 189 375 171 59 495 426 419 276 307 27 316 393 353 216 354 109 449 473 382 191 86 81 224 414 448 252 402 181 45 22 36 362 454 255 351 175 254 225 25 317 431 469 342 85 206 129 160 84 267 366 108 210 3...
result:
ok