QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#4827#439. 命运Qingyu100 ✓562ms193240kbC++112.5kb2020-08-20 18:36:332021-12-19 05:30:06

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2021-12-19 05:30:06]
  • 评测
  • 测评结果:100
  • 用时:562ms
  • 内存:193240kb
  • [2020-08-20 18:36:33]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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