QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#4827 | #439. 命运 | Qingyu | 100 ✓ | 562ms | 193240kb | C++11 | 2.5kb | 2020-08-20 18:36:33 | 2021-12-19 05:30:06 |
Judging History
answer
#include <bits/stdc++.h>
#define For(a, b, c) for (int a = b; a <= c; ++a)
#define Dor(a, b, c) for (int a = b; a >= c; --a)
using namespace std;
const int N = 500007, M = 40000000, P = 998244353;
int n, m, t, hd[N], nt[N << 1], to[N << 1], D[N], T[N], rt[N], ls[M], rs[M], F[M], G[M];
void walk(int u, int f = 0) {
D[u] = D[f] + 1;
for (int e = hd[u]; e; e = nt[e]) {
int v = to[e];
if (v == f)
continue;
walk(v, u);
}
}
int E(int u) { return !ls[u] && !rs[u]; }
void dn(int u) {
if (G[u] == 1 && !F[u])
return;
int &l = ls[u], &r = rs[u];
if (!l)
l = ++t, F[l] = 1;
if (!r)
r = ++t, F[r] = 1;
G[l] = 1LL * G[l] * G[u] % P, F[l] = (1LL * G[u] * F[l] + F[u]) % P;
G[r] = 1LL * G[r] * G[u] % P, F[r] = (1LL * G[u] * F[r] + F[u]) % P;
G[u] = 1, F[u] = 0;
}
int mrg(int x, int y) {
if (E(x) || E(y)) {
if (E(y))
swap(x, y);
G[y] = 1LL * F[x] * G[y] % P;
F[y] = 1LL * F[x] * F[y] % P;
return y;
}
dn(x), dn(y);
ls[x] = mrg(ls[x], ls[y]);
rs[x] = mrg(rs[x], rs[y]);
return x;
}
void clr(int &u, int l, int r, int L = 0, int R = n) {
if (l == L && r == R) {
ls[u] = rs[u] = G[u] = F[u] = 0;
return;
}
int M = (L + R) >> 1;
dn(u);
if (r <= M)
clr(ls[u], l, r, L, M);
else if (l > M)
clr(rs[u], l, r, M + 1, R);
else
clr(ls[u], l, M, L, M), clr(rs[u], M + 1, r, M + 1, R);
}
int qry(int &u, int x, int L = 0, int R = n) {
if (E(u))
return F[u];
int M = (L + R) >> 1;
dn(u);
if (x <= M)
return qry(ls[u], x, L, M);
return qry(rs[u], x, M + 1, R);
}
void fly(int u, int f = 0) {
rt[u] = ++t, F[t] = 1;
for (int e = hd[u]; e; e = nt[e]) {
int v = to[e];
if (v == f)
continue;
fly(v, u);
rt[u] = mrg(rt[u], rt[v]);
}
int s = qry(rt[u], D[u]);
if (T[u])
clr(rt[u], 0, T[u] - 1);
if (u > 1)
(F[rt[u]] += s) %= P;
}
int main() {
scanf("%d", &n);
int e = 0;
For(i, 1, n - 1) {
int x, y;
scanf("%d%d", &x, &y);
nt[++e] = hd[x], hd[x] = e, to[e] = y;
nt[++e] = hd[y], hd[y] = e, to[e] = x;
}
walk(1);
scanf("%d", &m);
For(i, 1, m) {
int x, y;
scanf("%d%d", &x, &y), T[y] = max(T[y], D[x] + 1);
}
fly(1);
int f = qry(rt[1], 0);
printf("%d", f);
return 0;
}
详细
Test #1:
score: 4
Accepted
time: 2ms
memory: 22112kb
input:
6 2 3 6 5 6 4 6 1 2 4 7 1 2 4 2 1 6 2 3 6 5 6 2 6 2
output:
2
result:
ok answer is '2'
Test #2:
score: 4
Accepted
time: 3ms
memory: 22060kb
input:
7 6 4 3 6 3 2 3 7 1 4 5 7 9 1 2 1 5 1 7 1 5 1 4 6 2 3 7 4 3 3 2
output:
6
result:
ok answer is '6'
Test #3:
score: 4
Accepted
time: 2ms
memory: 22108kb
input:
8 6 8 7 6 6 1 6 5 2 8 4 6 6 3 8 6 7 6 8 1 6 6 8 8 2 6 7 1 5 1 6
output:
8
result:
ok answer is '8'
Test #4:
score: 4
Accepted
time: 2ms
memory: 20072kb
input:
9 6 4 1 7 1 3 4 8 2 7 5 1 1 4 9 4 10 1 5 1 9 4 9 1 5 1 4 1 8 1 5 1 2 1 2 1 2
output:
24
result:
ok answer is '24'
Test #5:
score: 4
Accepted
time: 1ms
memory: 19976kb
input:
497 255 412 294 262 337 292 138 17 74 260 134 344 453 364 114 289 50 280 360 179 51 433 497 438 490 422 99 119 345 318 259 396 298 272 431 37 38 15 101 213 230 195 193 33 126 307 106 170 24 200 245 367 266 75 275 67 405 432 220 331 411 441 452 479 219 16 410 245 219 312 476 424 104 356 144 230 251 259 352 267 380 116 410 76 393 455 12 50 72 123 133 214 232 488 380 386 485 306 449 225 153 58 478 48 409 65 477 495 341 467 221 163 169 176 42 197 426 145 478 376 167 430 284 436 105 361 456 97 75 203...
output:
913693353
result:
ok answer is '913693353'
Test #6:
score: 4
Accepted
time: 5ms
memory: 22208kb
input:
10000 2286 4570 6005 8498 6796 7409 8543 5599 5964 3049 9689 64 555 8795 8719 1929 5814 6317 7104 2223 5537 4410 150 1311 9975 2583 8069 5198 6516 9798 7906 2340 9867 3843 1566 6050 4261 1981 6603 9122 7172 6996 9675 5124 6680 9947 920 1437 6693 4264 4977 7255 3707 2622 9914 4090 588 3714 147 7574 8531 6763 3688 4008 1823 9455 1496 4095 5661 2589 7099 2880 2769 9127 8831 7217 4028 3929 319 4421 6349 3943 4932 149 2566 8358 6316 8209 6915 1804 1109 1438 628 7584 415 1081 3634 7880 8645 8688 8749 ...
output:
741099208
result:
ok answer is '741099208'
Test #7:
score: 4
Accepted
time: 29ms
memory: 26184kb
input:
99999 24827 62592 58601 32988 9374 5313 16621 75518 13429 72361 72162 10410 19352 43426 50088 85249 60117 54428 45780 95257 71828 69234 45367 69122 8537 31711 19060 14175 49101 29413 77638 37540 14341 97505 86792 56691 24399 74996 48465 6197 84803 31855 79897 68879 43215 30590 32130 9225 41151 5727 25195 25736 33846 44771 25266 56373 93842 72121 65516 47164 73915 87926 32324 12592 91749 84205 99036 41272 4099 84101 81212 9977 55824 58395 90891 5290 35096 28194 24302 68577 59552 93327 43757 28412...
output:
298377224
result:
ok answer is '298377224'
Test #8:
score: 4
Accepted
time: 251ms
memory: 42332kb
input:
500000 481001 130369 33906 415753 490524 96079 164735 455776 70736 279997 378857 446203 146479 379023 277575 479123 279016 452847 157934 276420 365178 355559 92278 334178 384516 170203 53281 287053 91013 116371 66198 157826 439312 51593 299436 230757 87865 296922 14619 361816 196065 266068 333188 409985 177364 23132 265241 235708 232444 78586 232473 289720 253804 333901 158222 151925 358243 490026 49430 134319 79276 449049 246919 10177 260128 454652 134857 106559 231393 371015 373787 475295 1256...
output:
620543783
result:
ok answer is '620543783'
Test #9:
score: 4
Accepted
time: 23ms
memory: 26252kb
input:
99997 12420 85497 96299 96503 91359 61879 73963 53821 8421 57985 20625 76112 7710 49712 37822 48930 73283 21602 95544 63863 48109 71430 71156 13272 94319 85892 44636 21771 13012 32434 25568 67705 2402 72273 45184 77931 47042 90239 24095 8125 28880 6901 53229 34081 99484 60358 11889 94257 40320 63099 38970 56736 15893 58333 96792 68314 91765 28912 36753 54651 29672 77681 58249 28764 28448 27743 2489 86965 9953 96938 30280 83747 62538 38968 60555 65047 29971 1117 53841 38003 46643 73033 33624 4364...
output:
76263105
result:
ok answer is '76263105'
Test #10:
score: 4
Accepted
time: 224ms
memory: 37284kb
input:
499997 30888 482221 413340 184626 407235 423912 444162 164665 292046 377512 92865 497459 295659 434257 373183 130281 274974 165820 417090 329358 457165 135108 364466 306280 481928 272283 203252 229766 184132 104900 1319 197293 95369 415252 423790 88530 453001 268063 55065 23949 434123 184247 239979 323324 88406 134771 290819 456227 385198 403272 102833 482024 441926 188388 22962 282841 465642 256499 491039 140690 355158 235626 363601 408257 167237 490541 445124 371248 318036 417866 399233 385676...
output:
495702396
result:
ok answer is '495702396'
Test #11:
score: 4
Accepted
time: 4ms
memory: 22036kb
input:
598 495 238 121 55 369 328 139 276 230 262 309 232 357 183 521 350 177 193 557 336 214 12 285 13 137 36 353 208 81 470 361 583 226 418 88 364 280 252 428 338 216 142 35 584 62 326 27 594 151 6 425 339 159 464 209 224 598 294 312 90 466 185 108 374 253 379 524 289 389 458 78 446 332 319 511 21 468 166 534 507 182 16 274 590 439 518 283 435 549 366 412 589 339 194 2 275 454 584 160 551 316 548 106 406 26 428 59 432 544 244 470 134 443 377 26 401 343 150 499 303 448 187 222 204 304 61 70 323 14 511...
output:
422402046
result:
ok answer is '422402046'
Test #12:
score: 4
Accepted
time: 3ms
memory: 22068kb
input:
999 634 560 72 10 17 369 466 932 424 205 200 457 53 37 252 64 866 450 669 985 607 667 30 584 733 678 666 10 450 328 375 924 283 189 948 327 665 700 831 267 315 305 117 352 201 929 704 672 10 51 450 868 966 978 540 76 275 15 35 398 405 109 395 92 327 146 411 135 10 972 10 917 623 600 719 123 208 370 17 382 680 942 334 445 694 619 443 260 764 723 399 871 152 595 85 224 60 639 53 814 217 310 3 757 80 373 448 828 195 46 629 784 803 644 118 508 251 784 500 81 10 348 876 374 442 691 198 871 810 565 34...
output:
426197544
result:
ok answer is '426197544'
Test #13:
score: 4
Accepted
time: 69ms
memory: 22148kb
input:
1998 1129 982 64 915 984 1123 606 220 1624 1776 401 1840 159 370 1733 1699 753 317 559 1096 1443 152 1678 682 1033 1153 1745 350 1908 325 618 454 194 1195 786 1254 950 912 784 1582 333 910 32 279 1818 823 1426 990 1863 1182 1428 1526 1113 373 884 609 1113 270 1094 391 405 1440 784 959 998 1509 205 1174 1350 713 1019 1575 138 1236 1378 269 819 1348 1434 1848 546 1203 945 1473 1535 777 57 1527 45 1777 1044 1512 1349 236 759 89 1073 1956 1016 1414 488 1850 1303 1090 527 1126 59 478 1587 1039 1194 1...
output:
259778043
result:
ok answer is '259778043'
Test #14:
score: 4
Accepted
time: 79ms
memory: 24204kb
input:
1999 1039 956 987 1079 113 930 1411 1611 99 1121 115 1379 1811 835 855 44 78 378 833 1317 1642 841 1012 1411 1504 841 588 851 1565 1811 1411 1687 361 1712 1538 1411 819 584 477 1146 1014 1268 1956 366 430 287 1043 1294 910 1413 676 16 1024 1027 1915 841 1411 178 1399 1185 1937 158 1397 841 68 249 1306 1172 1411 1617 841 1134 1931 692 456 243 1282 242 1999 373 158 214 1446 311 827 20 1586 1425 732 35 1419 16 1411 1221 824 860 1411 1276 867 434 1087 224 1205 671 1411 802 494 1374 563 1449 420 1434...
output:
719079531
result:
ok answer is '719079531'
Test #15:
score: 4
Accepted
time: 214ms
memory: 49676kb
input:
499996 166429 374240 458250 186205 337525 397040 105532 121824 323632 293915 266697 417228 180442 297190 79265 219324 80328 16227 130791 321970 91028 57527 42303 425087 297432 223699 311644 18598 155816 2585 280416 329400 38048 413818 353672 18723 460086 20894 376884 401233 273015 96291 64286 98896 492244 221213 248500 203209 447737 498580 261167 450423 201022 410565 121824 269582 340521 82839 291199 29503 35435 322131 136652 387580 167264 333091 452855 366678 80197 123610 27036 227983 392284 38...
output:
440462992
result:
ok answer is '440462992'
Test #16:
score: 4
Accepted
time: 232ms
memory: 54220kb
input:
499999 429752 39010 87476 462988 436786 265632 313093 371847 150379 79799 292525 421113 461636 397528 468254 298152 329871 294594 374787 213141 349056 299400 157824 375747 127664 310858 51614 316107 247619 483715 99405 317027 451439 413890 271303 104915 14174 237451 72169 43889 267943 170586 111172 467992 246186 59439 449986 325311 177951 414040 467217 56157 240486 365386 171019 147376 152889 466912 332393 180057 159840 261228 288518 40866 253385 451888 138047 102767 220133 28395 66629 192957 43...
output:
503694719
result:
ok answer is '503694719'
Test #17:
score: 4
Accepted
time: 74ms
memory: 41284kb
input:
99997 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54 27 55 28 56 28 57 29 58 29 59 30 60 30 61 31 62 31 63 32 64 32 65 33 66 33 67 34 68 34 69 35 70 35 71 36 72 36 73 37 74 37 75 38 76 38 77 39 78 39 79 40 80 40 81 41 82 41 83 42 84 42 85 43 86 43 87 44 8...
output:
951546685
result:
ok answer is '951546685'
Test #18:
score: 4
Accepted
time: 53ms
memory: 38552kb
input:
100000 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54 27 55 28 56 28 57 29 58 29 59 30 60 30 61 31 62 31 63 32 64 32 65 33 66 33 67 34 68 34 69 35 70 35 71 36 72 36 73 37 74 37 75 38 76 38 77 39 78 39 79 40 80 40 81 41 82 41 83 42 84 42 85 43 86 43 87 44 ...
output:
398299966
result:
ok answer is '398299966'
Test #19:
score: 4
Accepted
time: 46ms
memory: 36748kb
input:
49994 16773 18084 13652 26028 29320 22500 8168 20391 20712 13289 18306 48732 1147 32403 22074 29376 42713 11128 26847 2494 20937 3907 44148 35349 27897 4800 7299 31995 33721 5113 31418 10206 19747 35922 10414 25963 18776 42084 44938 6516 4800 5329 41176 17864 31066 12752 29923 33698 47504 37268 47242 35133 6021 27860 22341 13249 37323 44938 48458 44938 44761 10492 21077 35602 17262 16002 506 21517 1317 9688 44938 7507 40068 2694 2032 33142 32314 43135 44938 23010 22924 21715 14356 5870 26433 358...
output:
311193151
result:
ok answer is '311193151'
Test #20:
score: 4
Accepted
time: 93ms
memory: 45476kb
input:
79998 15767 34291 71245 14457 74445 58864 16367 6779 48359 64486 19508 48504 62217 20603 37223 443 59509 35966 38405 16920 79413 77556 27559 51976 66736 3647 41686 52728 46231 43331 34940 36057 61287 64199 76627 37116 21332 78604 27326 78434 58838 67326 24178 59289 10708 15944 14521 15352 23285 25432 54980 18827 19508 55738 17512 78932 31877 3531 28338 37456 37227 19508 58693 2527 22516 32714 6193 49445 30424 57636 79413 70189 31452 39086 17732 32617 15535 18132 59667 37593 60370 39257 14025 429...
output:
108272378
result:
ok answer is '108272378'
Test #21:
score: 4
Accepted
time: 227ms
memory: 63252kb
input:
99999 14680 98099 68941 56143 16160 83923 32354 64072 19605 7048 24721 7369 32025 33248 57959 42630 48493 52559 48493 15160 76901 41756 31947 88634 98862 48493 70561 81999 81064 6357 29348 88172 36474 76470 70131 49915 12930 22381 25437 70561 70561 56236 70561 43957 17512 54072 48987 9540 42841 21545 11631 85396 70561 88336 65091 19874 15454 66779 33876 16528 19629 48493 44522 90877 96977 70131 89069 70561 70131 83792 93504 26386 70561 44514 48493 59308 11730 35542 49631 33732 83107 48493 78179 ...
output:
38247969
result:
ok answer is '38247969'
Test #22:
score: 4
Accepted
time: 154ms
memory: 58616kb
input:
99996 81219 46611 27070 96230 88963 28320 47132 90466 47025 55027 56136 29854 12528 51209 51703 49946 85094 23069 28768 29508 51373 56376 21628 27271 75141 74333 86616 42671 47071 81610 71794 38614 95689 68213 21472 76729 95826 1 7067 56421 9255 1 46816 26963 68196 56713 83546 84190 92874 63215 47991 61770 32793 76977 20771 9519 83630 3189 47972 47356 59410 81924 19067 1 52512 71483 1958 12600 64537 53537 43121 83817 39379 1 53349 19843 41216 17594 64 38911 57394 96987 24469 22821 89239 19493 73...
output:
881239389
result:
ok answer is '881239389'
Test #23:
score: 4
Accepted
time: 556ms
memory: 189972kb
input:
499999 328444 232129 34137 337939 1 2770 145619 337672 223675 257443 252889 184274 435369 80009 390302 338638 87899 38243 328444 374192 95368 379319 203463 293410 158770 373327 153849 111860 303903 481356 129222 216039 287062 175092 485781 979 359098 421597 5354 229733 227881 30640 142194 126688 344807 66446 141082 126713 429188 440909 450069 267933 78904 476286 292736 480342 391929 37948 115132 31213 136640 24806 214311 176267 274022 140151 483851 69980 328444 99771 349311 217678 465504 348196 ...
output:
213231046
result:
ok answer is '213231046'
Test #24:
score: 4
Accepted
time: 562ms
memory: 193240kb
input:
499996 234812 237052 231031 104664 102145 299812 273901 51367 487834 495839 77385 276903 393563 119918 136245 318870 68288 88488 185218 237190 347758 398936 492387 460746 287846 454723 400936 222847 77067 485362 113343 113127 25637 124859 146819 460819 118564 204986 1597 420874 406709 470358 318130 234894 264019 1 363871 283502 427837 40489 377552 346737 299453 134192 352 322469 224532 173402 390593 350236 89866 29144 497218 351317 242290 340452 485650 20581 475681 166789 218532 208278 1280 4034...
output:
775170
result:
ok answer is '775170'
Test #25:
score: 4
Accepted
time: 555ms
memory: 192172kb
input:
499999 413164 1 45178 10034 77624 1 1 295033 113198 162474 5742 45178 76083 379306 271416 134250 130336 491344 426378 1 10340 45178 14040 430225 1 468965 210040 482376 22963 473681 173835 464785 73841 103763 209733 383125 469692 1 1 14003 375214 363310 45178 208777 16359 260731 340784 490818 491344 492077 91062 101683 382393 486670 445148 430225 179689 79242 87471 1 61524 217620 411235 305617 293313 45178 1 178451 417472 48708 256375 1 214050 161421 1 212270 1 411255 1 392438 488000 430225 45178...
output:
247536705
result:
ok answer is '247536705'
Extra Test:
score: 0
Extra Test Passed