QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#576584#8078. Spanning Treexinhuo2005AC ✓406ms86952kbC++202.2kb2024-09-19 21:09:212024-09-19 21:09:21

Judging History

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

  • [2024-09-19 21:09:21]
  • 评测
  • 测评结果:AC
  • 用时:406ms
  • 内存:86952kb
  • [2024-09-19 21:09:21]
  • 提交

answer

#include<bits/stdc++.h>
using ll = long long;
const int mod = 998244353;

inline ll qpow(ll a, ll b) {
    if (b == 0) return 1ll;
    if (b == 1) return a;
    ll res = qpow(a, b / 2);
    res = res * res % mod;
    if (b & 1) return res * a % mod;
    return res;
}

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> fa(n), dep(n), siz(n), p(n);
    std::vector<std::vector<int>> adj(n);
    std::vector<std::pair<int, int>> a(n - 1);
    for (int i = 0; i < n - 1; i++) {
        std::cin >> a[i].first >> a[i].second;
        a[i].first --;
        a[i].second --;
    }

    for (int i = 1; i < n; i++) {
        int x, y;
        std::cin >> x >> y;
        x--; y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    auto dfs = [&](auto& self, int u, int fno) -> void {
        for (auto v : adj[u]) {
            if (v == fno) continue;
            p[v] = u;
            dep[v] = dep[u] + 1;
            self(self, v, u);
        }
    };

    dfs(dfs, 0, -1);
    for (int i = 0; i < n; i++) fa[i] = i, siz[i] = 1;
    
    auto find = [&](auto& self, int x) -> int {
        if (fa[x] == x) {
            return x;
        }
        int t = self(self, fa[x]);
        fa[x] = t;
        return t;
    };
    auto merge = [&](int x, int y) {
        x = find(find, x);
        y = find(find, y);
        if (dep[x] < dep[y]) std::swap(x, y);
        fa[x] = y;
        dep[x] = dep[y];
        siz[y] += siz[x];
    };

    ll ans = 1;
    for (int i = 0; i < n - 1; i++) {
        int x = a[i].first, y = a[i].second;
        int fx = find(find, x), fy = find(find, y);
        if (dep[fx] < dep[fy]) std::swap(fx, fy);
        int fx1 = find(find, p[fx]);
        if (fx1 == fy) {
            ans = ((ans * siz[fx]) % mod) * siz[fy] % mod;
            merge(x, y);
        }
        else {
            std::cout << 0 << "\n";
            return ;
        }

    }
    std::cout << qpow(ans, mod - 2) << "\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t = 1;
    // std::cin >> t;

    while (t--) {
        solve();
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3884kb

input:

3
1 2
1 3
1 2
1 3

output:

499122177

result:

ok single line: '499122177'

Test #2:

score: 0
Accepted
time: 28ms
memory: 11020kb

input:

100000
2183 5543
22424 59062
8387 24544
14668 74754
15788 58136
26846 99981
13646 57752
29585 62862
27383 65052
2013 13116
24490 91945
26006 61595
19000 78817
31371 67837
29311 82989
4298 20577
23212 77962
16510 85839
26010 98714
25314 96063
17206 82359
7478 76540
13890 99556
23277 64321
25684 92613...

output:

330864231

result:

ok single line: '330864231'

Test #3:

score: 0
Accepted
time: 32ms
memory: 10996kb

input:

100000
2431 82555
18148 99107
3941 5966
1071 47115
15967 53202
27778 80193
17295 91006
21981 69106
8487 92235
7229 17953
6531 81170
18678 84896
25646 98753
3087 34488
4008 80883
18556 30802
250 3839
10378 92520
27250 87378
18484 75316
12912 82770
6142 78903
18637 58366
5716 82933
25060 76764
7868 78...

output:

207623640

result:

ok single line: '207623640'

Test #4:

score: 0
Accepted
time: 36ms
memory: 10972kb

input:

100000
3677 53591
26136 80586
14460 75864
5626 70315
2145 17733
681 92982
19076 64996
1672 82873
7909 80493
1362 87683
3121 81083
1881 92956
19448 31658
26638 78109
17888 74591
31114 97492
30263 93965
15990 51796
25387 47368
26827 50839
21100 85993
8497 95004
3017 3343
12299 97797
16723 59533
19266 ...

output:

315464493

result:

ok single line: '315464493'

Test #5:

score: 0
Accepted
time: 27ms
memory: 11000kb

input:

100000
337 80784
277 63525
309 68073
50 65780
223 85983
229 99952
419 97414
210 73844
149 98533
19 92591
254 75626
413 28608
31 13397
355 9807
248 86299
177 92507
75 77718
238 94072
440 73716
34 33639
39 92470
177 76740
210 93812
460 86098
79 38556
500 4414
306 93377
341 46557
260 18020
170 70281
99...

output:

782103077

result:

ok single line: '782103077'

Test #6:

score: 0
Accepted
time: 34ms
memory: 11016kb

input:

100000
77 61768
159 75045
189 96344
27 90011
80 70404
100 10876
196 6710
83 69730
122 61478
95 34246
121 66123
76 91590
183 84813
30 22860
21 64208
197 52093
136 95550
104 74693
141 43684
76 24573
180 96323
27 63135
78 77847
110 49459
67 89691
82 98960
53 62386
94 95145
15 72896
28 92579
145 94344
9...

output:

574681591

result:

ok single line: '574681591'

Test #7:

score: 0
Accepted
time: 31ms
memory: 10996kb

input:

100000
7 93472
18 98769
12 97619
17 73647
10 16818
1 91671
7 87544
6 72485
3 92155
8 72652
13 69083
18 95717
19 96402
6 18778
9 99294
18 90017
17 79729
14 97967
11 92694
8 63979
10 97859
7 44859
2 85081
4 58827
18 98750
6 75751
11 94889
4 22678
8 84842
15 84960
5 76729
2 90310
19 55608
12 87558
16 9...

output:

45611347

result:

ok single line: '45611347'

Test #8:

score: 0
Accepted
time: 32ms
memory: 11004kb

input:

100000
7 58890
3 58280
7 27055
7 93537
1 91565
5 88595
4 84795
3 87969
5 98167
3 89215
8 68189
1 9565
2 75124
5 57314
2 80828
6 69452
7 94539
5 95670
2 69584
7 58461
2 88826
4 60983
4 64741
5 94797
5 85145
3 63668
3 29256
2 80180
3 1473
7 34495
3 25487
6 49093
4 92049
6 32240
6 60954
1 23309
2 7334
...

output:

359179257

result:

ok single line: '359179257'

Test #9:

score: 0
Accepted
time: 28ms
memory: 11544kb

input:

100000
7 52065
5 79374
8 93846
5 98472
10 72503
4 54043
2 81067
5 25410
9 66642
4 96261
2 69048
5 53093
8 72619
5 25253
7 92182
10 85942
2 96401
10 56808
1 65642
4 94067
8 76278
5 92554
5 16028
8 95421
9 96769
9 38660
4 37431
6 89486
5 12160
5 96259
3 84728
1 51495
4 96438
6 49380
1 95929
1 27527
8 ...

output:

407203766

result:

ok single line: '407203766'

Test #10:

score: 0
Accepted
time: 22ms
memory: 11600kb

input:

100000
78 73288
63 78335
71 60255
14 89232
33 31513
96 31412
63 64415
87 60736
56 60604
9 91650
29 86482
65 90995
94 91106
15 93202
56 15471
69 40408
83 88007
42 94851
33 68754
81 58316
87 69603
1 17260
95 78585
8 39063
58 31243
20 13440
94 53628
17 88933
58 98863
65 93116
22 82543
28 86883
27 59282...

output:

517010519

result:

ok single line: '517010519'

Test #11:

score: 0
Accepted
time: 26ms
memory: 11600kb

input:

100000
442 69813
189 43985
356 86661
74 29978
381 51503
808 84079
837 91324
12 91061
238 90167
910 98749
28 45930
834 97170
636 56426
592 99796
752 67695
489 66396
688 49989
151 94252
280 5651
363 78766
223 93772
937 84602
336 78368
264 74532
701 54957
277 78254
891 97873
637 22363
582 43788
887 873...

output:

968562725

result:

ok single line: '968562725'

Test #12:

score: 0
Accepted
time: 35ms
memory: 11084kb

input:

100000
31518 99113
23679 31891
224 4623
1819 48802
11333 71708
11245 92859
8309 75148
10033 89063
297 93596
18282 88408
16020 98356
27633 30998
15471 53295
8023 78199
25209 44744
27250 66553
27805 70208
31835 62514
8589 42520
10650 99871
2095 21829
21341 40322
4584 98667
25361 87279
25248 30530
2625...

output:

0

result:

ok single line: '0'

Test #13:

score: 0
Accepted
time: 36ms
memory: 10972kb

input:

100000
29557 93649
10753 56671
24466 72701
1384 99687
6546 20050
17335 97139
602 85076
27423 94808
6671 69540
9012 24231
22086 89387
3911 53451
1125 24156
15603 93219
21598 95879
29120 77832
1122 77121
30596 78906
3562 20826
9711 58720
26577 93105
1239 74813
22634 90533
16580 70202
9151 91423
9138 3...

output:

0

result:

ok single line: '0'

Test #14:

score: 0
Accepted
time: 32ms
memory: 10972kb

input:

100000
11052 93507
32763 42377
3539 95722
28478 42428
28822 73108
17800 32034
21291 54942
32182 98922
28240 87649
27633 91285
29059 51198
2192 5282
29820 87910
12552 94901
32374 98661
6618 61155
16911 39354
17408 83301
13524 84942
16147 92960
16986 82804
2008 98635
16746 30250
25311 90367
27942 6702...

output:

0

result:

ok single line: '0'

Test #15:

score: 0
Accepted
time: 31ms
memory: 11280kb

input:

100000
21541 68499
23622 95286
19569 92366
17503 86493
1973 88783
26799 91342
13858 84932
2055 99415
11930 40465
8120 94109
19501 71619
8091 18971
19457 64055
12649 71789
16657 89312
29364 94208
10524 90079
4147 97402
6424 93538
22519 57930
19027 74021
555 99344
19677 85788
30071 45237
12313 51129
2...

output:

0

result:

ok single line: '0'

Test #16:

score: 0
Accepted
time: 357ms
memory: 86644kb

input:

1000000
6469 999561
13878 967683
21843 921179
25097 928554
25703 987943
14790 975820
8363 975184
19685 962213
22207 995737
13821 985366
6646 992255
32437 895192
16156 984517
13685 875123
3856 988805
16070 969018
32049 962285
23741 935777
23886 949268
11506 993212
25067 999053
30691 970950
15900 9574...

output:

464421553

result:

ok single line: '464421553'

Test #17:

score: 0
Accepted
time: 386ms
memory: 86452kb

input:

1000000
24460 991332
13731 995432
19665 962294
11791 931863
16817 983768
2476 965018
21135 986410
10868 966675
17874 902265
3570 991677
30055 996521
15049 999752
3413 978934
30326 998661
12433 933275
28362 989240
20699 982498
31977 943563
17769 954244
20208 847131
17105 987971
20504 932740
4492 9736...

output:

350281136

result:

ok single line: '350281136'

Test #18:

score: 0
Accepted
time: 378ms
memory: 86716kb

input:

1000000
28952 996417
17066 932556
5743 911369
28860 982310
14301 986505
14664 937389
13014 959886
19545 968149
4944 993650
399 976740
19170 914240
433 952498
14941 990812
25332 953473
16683 987881
17426 997236
24448 969512
8401 985738
32362 975148
6720 952065
2307 991749
22850 980861
15563 958746
22...

output:

0

result:

ok single line: '0'

Test #19:

score: 0
Accepted
time: 337ms
memory: 86952kb

input:

1000000
5 999616
3 981589
4 982343
3 943412
7 977031
9 987917
3 967503
2 991224
8 983302
4 992890
2 998540
3 939547
7 971894
7 980040
5 957826
10 996349
6 920320
4 993400
9 932059
9 926717
9 989097
7 963426
4 991299
1 962259
3 966061
7 998494
3 985841
10 992365
6 940521
5 988510
5 994769
4 998924
4 ...

output:

686034512

result:

ok single line: '686034512'

Test #20:

score: 0
Accepted
time: 389ms
memory: 81624kb

input:

1000000
950745 950753
917659 917667
979197 979200
980702 980707
888623 888628
950893 950900
942855 942859
953554 953564
987763 987766
976676 976685
970411 970413
941064 941066
998771 998779
973556 973562
930906 930916
986740 986746
997129 997134
993273 993281
976350 976358
957912 957918
981118 98111...

output:

753456475

result:

ok single line: '753456475'

Test #21:

score: 0
Accepted
time: 406ms
memory: 81688kb

input:

1000000
975017 975020
981730 981731
987640 987649
974670 974671
988401 988408
986676 986683
970961 970962
921748 921749
991382 991389
945956 945959
995359 995361
936576 936586
975980 975986
890202 890204
926343 926347
928132 928142
995397 995401
974929 974934
993848 993853
886991 886997
903247 90325...

output:

0

result:

ok single line: '0'

Extra Test:

score: 0
Extra Test Passed