QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#576584 | #8078. Spanning Tree | xinhuo2005 | AC ✓ | 406ms | 86952kb | C++20 | 2.2kb | 2024-09-19 21:09:21 | 2024-09-19 21:09:21 |
Judging History
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