QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#290681 | #439. 命运 | MoRanSky | 100 ✓ | 716ms | 193012kb | C++23 | 2.7kb | 2023-12-25 06:25:41 | 2023-12-25 06:25:42 |
Judging History
answer
#include <iostream>
#include <cstdio>
#define ls t[p].l
#define rs t[p].r
using namespace std;
typedef long long LL;
const int N = 500005, P = 998244353;
int n, m, dep[N], L, g[N], rt[N], w1, w2;
int head[N], numE = 1;
struct E{
int next, v;
} e[N << 1];
void inline add(int u, int v) {
e[++numE] = (E) { head[u], v };
head[u] = numE;
}
void dfs(int u, int fa) {
L = max(L, dep[u]);
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (v == fa) continue;
dep[v] = dep[u] + 1;
dfs(v, u);
}
}
int idx;
struct T{
int l, r, sum, tag;
} t[N * 20];
void inline pushdown(int p) {
if (t[p].tag != 1) {
t[ls].sum = (LL)t[ls].sum * t[p].tag % P;
t[rs].sum = (LL)t[rs].sum * t[p].tag % P;
t[ls].tag = (LL)t[ls].tag * t[p].tag % P;
t[rs].tag = (LL)t[rs].tag * t[p].tag % P;
t[p].tag = 1;
}
}
void inline pushup(int p) {
t[p].sum = (t[ls].sum + t[rs].sum) % P;
}
void build(int &p, int l, int r, int x) {
t[p = ++idx].tag = 1;
if (l == r) { t[p].sum = 1; return; }
int mid = (l + r) >> 1;
if (x <= mid) build(t[p].l, l, mid, x);
else build(t[p].r, mid + 1, r, x);
pushup(p);
}
int query(int p, int l, int r, int x, int y) {
if (!p) return 0;
if (x <= l && r <= y) return t[p].sum;
pushdown(p);
int mid = (l + r) >> 1, res = 0;
if (x <= mid) (res += query(t[p].l, l, mid, x, y)) %= P;
if (mid < y) (res += query(t[p].r, mid + 1, r, x, y)) %= P;
return res;
}
void merge(int &p, int q, int l, int r) {
if (!p && !q) return;
if (!p) {
p = q; (w1 += t[p].sum) %= P;
t[p].sum = (LL)t[p].sum * w2 % P;
t[p].tag = (LL)t[p].tag * w2 % P;
return;
}
if (!q) {
(w2 += t[p].sum) %= P;
t[p].sum = (LL)t[p].sum * w1 % P;
t[p].tag = (LL)t[p].tag * w1 % P;
return;
}
if (l == r) {
int x = t[q].sum, y = t[p].sum;
(w1 += x) %= P;
t[p].sum = ((LL)y * w1 + (LL)x * w2) % P;
(w2 += y) %= P;
return;
}
pushdown(p); pushdown(q);
int mid = (l + r) >> 1;
merge(t[p].l, t[q].l, l, mid);
merge(t[p].r, t[q].r, mid + 1, r);
pushup(p);
}
void dfs2(int u, int fa) {
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (v == fa) continue;
dfs2(v, u);
w1 = query(rt[v], 0, L, 0, dep[u]), w2 = 0;
merge(rt[u], rt[v], 0, L);
}
}
int main() {
//freopen("destiny.in", "r", stdin);
//freopen("destiny.out", "w", stdout);
scanf("%d", &n);
for (int i = 1, u, v; i < n; i++)
scanf("%d%d", &u, &v), add(u, v), add(v, u);
dep[1] = 1; dfs(1, 0);
scanf("%d", &m);
for (int i = 1, u, v; i <= m; i++) {
scanf("%d%d", &u, &v);
g[v] = max(g[v], dep[u]);
}
for (int i = 1; i <= n; i++) build(rt[i], 0, L, g[i]);
dfs2(1, 0);
printf("%d\n", query(rt[1], 0, L, 0, 0));
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 4
Accepted
time: 1ms
memory: 3652kb
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: 0ms
memory: 3648kb
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: 0ms
memory: 3892kb
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: 1ms
memory: 3848kb
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: 3756kb
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 2...
output:
913693353
result:
ok answer is '913693353'
Test #6:
score: 4
Accepted
time: 5ms
memory: 5980kb
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 8...
output:
741099208
result:
ok answer is '741099208'
Test #7:
score: 4
Accepted
time: 59ms
memory: 33468kb
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 ...
output:
298377224
result:
ok answer is '298377224'
Test #8:
score: 4
Accepted
time: 496ms
memory: 167968kb
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 40...
output:
620543783
result:
ok answer is '620543783'
Test #9:
score: 4
Accepted
time: 62ms
memory: 33324kb
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...
output:
76263105
result:
ok answer is '76263105'
Test #10:
score: 4
Accepted
time: 494ms
memory: 167004kb
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 ...
output:
495702396
result:
ok answer is '495702396'
Test #11:
score: 4
Accepted
time: 0ms
memory: 3772kb
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 16...
output:
422402046
result:
ok answer is '422402046'
Test #12:
score: 4
Accepted
time: 1ms
memory: 3872kb
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 ...
output:
426197544
result:
ok answer is '426197544'
Test #13:
score: 4
Accepted
time: 41ms
memory: 4188kb
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 1...
output:
259778043
result:
ok answer is '259778043'
Test #14:
score: 4
Accepted
time: 47ms
memory: 4164kb
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 13...
output:
719079531
result:
ok answer is '719079531'
Test #15:
score: 4
Accepted
time: 508ms
memory: 187164kb
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 ...
output:
440462992
result:
ok answer is '440462992'
Test #16:
score: 4
Accepted
time: 504ms
memory: 193012kb
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 ...
output:
503694719
result:
ok answer is '503694719'
Test #17:
score: 4
Accepted
time: 34ms
memory: 15584kb
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...
output:
951546685
result:
ok answer is '951546685'
Test #18:
score: 4
Accepted
time: 38ms
memory: 15356kb
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 2...
output:
398299966
result:
ok answer is '398299966'
Test #19:
score: 4
Accepted
time: 45ms
memory: 19496kb
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 4724...
output:
311193151
result:
ok answer is '311193151'
Test #20:
score: 4
Accepted
time: 79ms
memory: 30408kb
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 2543...
output:
108272378
result:
ok answer is '108272378'
Test #21:
score: 4
Accepted
time: 135ms
memory: 33544kb
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 2154...
output:
38247969
result:
ok answer is '38247969'
Test #22:
score: 4
Accepted
time: 145ms
memory: 36104kb
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 4799...
output:
881239389
result:
ok answer is '881239389'
Test #23:
score: 4
Accepted
time: 625ms
memory: 173476kb
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 344...
output:
213231046
result:
ok answer is '213231046'
Test #24:
score: 4
Accepted
time: 716ms
memory: 192324kb
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 ...
output:
775170
result:
ok answer is '775170'
Test #25:
score: 4
Accepted
time: 565ms
memory: 169936kb
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 ...
output:
247536705
result:
ok answer is '247536705'
Extra Test:
score: 0
Extra Test Passed