QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#692850#8. 奇数国0002260 0ms0kbC++171.6kb2024-10-31 15:07:422024-10-31 15:07:55

Judging History

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

  • [2024-10-31 15:07:55]
  • 评测
  • 测评结果：0
  • 用时：0ms
  • 内存：0kb
查看
  • [2024-10-31 15:07:42]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

const int P = 998244353;

inline int power(int x, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = 1ll * res * x % P;
        x = 1ll * x * x % P; k >>= 1;
    } return res;
}

const int N = 1e5 + 5;

int n;
vector<int> e[N];

int Ans;
int sz[N];
int f[N];
int ss[N];

void dfs0(int x, int fx) {
    ss[x] = 1;
    for (int y : e[x]) if (y != fx)
        dfs0(y, x), ss[x] += ss[y];
}

void dfs1(int x, int fx, int nowsum) {
    //sz[x] = 1;
    //f[x] = 1 * 1;
    f[x] = 0;
    sz[x] = 0;
    for (int y : e[x]) 
        if (y != fx) {
            dfs1 (y, x, (nowsum + 1ll * (n - ss[y] + 1) * (n - ss[y] + 1) ) % P); //
            Ans = (Ans + 1ll * f[x] * f[y]) % P;
            f[x] = (f[x] + f[y]) % P;
            sz[x] += sz[y];
        }
    Ans = (Ans + 1ll * nowsum * f[x]) % P;
    sz[x] ++;
    f[x] = (f[x] + 1ll * sz[x] * sz[x]) % P;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i ++) e[i].clear();
    for (int i = 2; i <= n; i ++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back (y);
        e[y].push_back (x);
    }
    Ans = 0;
    dfs0(1, 0);
    dfs1 (1, 0, 1);

    cerr << Ans << endl;

    int inv = 1ll * n * (n - 1) / 2 % P;
    inv = power (inv, P - 2);
    Ans = 1ll * Ans * inv % P * inv % P;
    cout << Ans << '\n';
}

int main() {
    ios :: sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int Case;
    cin >> Case;
    while (Case --) solve();
    return 0;
}
源文件, 语言: C++17

详细


Pretests


Final Tests

Test #1:

score: 0
Memory Limit Exceeded

input:

122
1 47 84606
1 39 10304
0 31 46
0 47 50
1 16 80142
1 15 55620
1 56 8487
1 22 65813
0 17 28
1 45 73139
0 41 47
1 15 73640
1 40 44390
1 68 70490
0 63 69
0 39 40
0 12 16
1 25 3444
0 25 27
1 18 31800
1 60 89056
1 60 52890
0 53 60
0 53 60
1 63 3243
1 54 9100
0 51 59
1 35 36461
1 61 52428
0 55 61
1 50 6...

output:

result:

Test #2:

score: 0
Memory Limit Exceeded

input:

10000
1 3204 2085
0 3193 3210
0 5567 5581
0 5070 5093
1 7744 53578
0 7726 7744
1 5938 90890
0 5933 5946
1 2282 404
0 2275 2293
0 5529 5552
0 5411 5427
1 1288 83658
1 1691 75254
1 8728 1909
1 9085 92560
0 9068 9085
0 8728 8731
1 6452 52632
0 6444 6458
0 1691 1704
0 1270 1288
0 5233 5248
0 5400 5420
0...

output:

result:

Test #3:

score: 0
Runtime Error

input:

20000
0 4519 6399
0 5538 5991
0 5830 7147
1 5838 256887
0 5544 7321
1 3889 10561
1 2843 775260
0 1555 2973
0 2570 5389
0 5338 6500
1 9416 950309
1 5569 690690
1 3145 135315
1 2365 35167
1 3940 43
1 5310 5353
1 8337 568841
1 5796 169
1 3104 746130
0 2515 3432
1 10626 35611
0 8635 12588
1 10562 946774...

output:

result:

Test #4:

score: 0
Runtime Error

input:

30000
1 12080 458075
0 9890 15050
1 7144 149
0 4091 10808
1 5942 843378
0 2599 9264
1 9921 6647
0 6378 12730
1 8131 602651
0 5475 11565
1 9005 870870
0 6625 12774
1 11492 690690
0 8194 14863
1 4340 256
0 918 6863
1 7069 344488
0 3763 10001
1 12418 8192
0 9118 15941
1 11125 690690
0 8462 14279
1 9951...

output:

result:

Test #5:

score: 0
Runtime Error

input:

50000
1 29347 187726
0 25914 32532
1 20674 8192
0 15953 24784
1 24117 4752
0 19706 27975
1 22413 538
0 18457 27027
1 25177 931944
0 20749 29602
1 25822 52728
0 22542 28875
1 27405 746130
0 23587 31278
1 24494 24187
0 20318 27988
1 23628 85158
0 20006 28203
1 20524 24389
0 16166 24111
1 29127 733825
...

output:

result:

Test #6:

score: 0
Runtime Error

input:

60000
1 6 2
1 12 3
1 18 5
1 24 7
1 30 11
1 36 13
1 42 17
1 48 19
1 54 23
1 60 29
1 66 31
1 72 37
1 78 41
1 84 43
1 90 47
1 96 53
1 102 59
1 108 61
1 114 67
1 120 71
1 126 73
1 132 79
1 138 83
1 144 89
1 150 97
1 156 101
1 162 103
1 168 107
1 174 109
1 180 113
1 186 127
1 192 131
1 198 137
1 204 139
...

output:

0
545706913
0
502063232
0
337860817
0
42519177
0
767564588

result:

Test #7:

score: 0
Runtime Error

input:

70000
1 7 2
1 14 3
1 21 5
1 28 7
1 35 11
1 42 13
1 49 17
1 56 19
1 63 23
1 70 29
1 77 31
1 84 37
1 91 41
1 98 43
1 105 47
1 112 53
1 119 59
1 126 61
1 133 67
1 140 71
1 147 73
1 154 79
1 161 83
1 168 89
1 175 97
1 182 101
1 189 103
1 196 107
1 203 109
1 210 113
1 217 127
1 224 131
1 231 137
1 238 13...

output:

0
436873379
626666455
690558345
0
444838155
384972972
0
909901670
0

result:

Test #8:

score: 0
Runtime Error

input:

80000
1 8 2
1 16 3
1 24 5
1 32 7
1 40 11
1 48 13
1 56 17
1 64 19
1 72 23
1 80 29
1 88 31
1 96 37
1 104 41
1 112 43
1 120 47
1 128 53
1 136 59
1 144 61
1 152 67
1 160 71
1 168 73
1 176 79
1 184 83
1 192 89
1 200 97
1 208 101
1 216 103
1 224 107
1 232 109
1 240 113
1 248 127
1 256 131
1 264 137
1 272 ...

output:

0
836538954
379908774
0
722336342
605132936
371211325
916379314
0
538598545
513377184
176560226

result:

Test #9:

score: 0
Runtime Error

input:

90000
1 9 2
1 18 3
1 27 5
1 36 7
1 45 11
1 54 13
1 63 17
1 72 19
1 81 23
1 90 29
1 99 31
1 108 37
1 117 41
1 126 43
1 135 47
1 144 53
1 153 59
1 162 61
1 171 67
1 180 71
1 189 73
1 198 79
1 207 83
1 216 89
1 225 97
1 234 101
1 243 103
1 252 107
1 261 109
1 270 113
1 279 127
1 288 131
1 297 137
1 306...

output:

0
25418259
0
776802495
0
355661833
0
820624991

result:

Test #10:

score: 0
Runtime Error

input:

100000
1 10 2
1 20 3
1 30 5
1 40 7
1 50 11
1 60 13
1 70 17
1 80 19
1 90 23
1 100 29
1 110 31
1 120 37
1 130 41
1 140 43
1 150 47
1 160 53
1 170 59
1 180 61
1 190 67
1 200 71
1 210 73
1 220 79
1 230 83
1 240 89
1 250 97
1 260 101
1 270 103
1 280 107
1 290 109
1 300 113
1 310 127
1 320 131
1 330 137
1...

output:

0
933173610
348759462
916379314
0
77709725

result:
English 繁體中文 简体中文

服务器时间: 2025-01-20 07:11:48 | 开源项目