QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#85648#2061. Inspectiontriplem5ds#AC ✓109ms28040kbC++201.7kb2023-03-08 00:08:012023-03-08 00:08:01

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-08 00:08:01]
  • 评测
  • 测评结果:AC
  • 用时:109ms
  • 内存:28040kb
  • [2023-03-08 00:08:01]
  • 提交

answer

///Enta etfsh5t nseet el rank

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
        tree_order_statistics_node_update>;
#define pb push_back
#define F first
#define S second
#define f(i, a, b) for (int i = a; i < b; i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(x) (int)(x).size()
#define mp(x, y) make_pair(x, y)
#define popCnt(x) (__builtin_popcountll(x))
#define int ll

using ll = long long;
using ull = unsigned long long;
using uint = uint32_t;
using ii = pair<int, int>;

const int N = 5e5 + 6, LG = 18, MOD = (119 << 23) + 1;
const long double PI = acos(-1);
const long double EPS = 1e-9;
const ll INF = 1e15;

int dp1[N], dp2[N];
vector<int> adj[N];
int sz[N];

void dfs(int node, int par) {
    sz[node] = 1;
    for (auto v: adj[node])
        if (v != par) {
            dfs(v, node);
            sz[node] += sz[v];
        }
}

void doWork() {

    int n;
    cin >> n;
    f(i, 1, n) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfs(1, 1);
    int ans = 0;
    f(i, 2, n + 1)ans = (ans + sz[i] * (n - sz[i]));
    cout << ans << '\n';

}


int32_t main() {
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif // ONLINE_JUDGE

    int t = 1;
//    cin >> t;
    while (t--)
        doWork();

    return 0;
}

详细

Test #1:

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

input:

5
1 2
1 3
3 4
3 5

output:

18

result:

ok answer is '18'

Test #2:

score: 0
Accepted
time: 1ms
memory: 15244kb

input:

2
2 1

output:

1

result:

ok answer is '1'

Test #3:

score: 0
Accepted
time: 5ms
memory: 15280kb

input:

1

output:

0

result:

ok answer is '0'

Test #4:

score: 0
Accepted
time: 10ms
memory: 15128kb

input:

3
3 1
2 3

output:

4

result:

ok answer is '4'

Test #5:

score: 0
Accepted
time: 1ms
memory: 16052kb

input:

111
34 23
46 76
96 50
32 65
13 55
40 60
21 3
88 33
108 20
99 30
52 81
105 36
39 66
92 24
56 92
41 38
66 64
94 13
46 69
90 102
96 91
34 10
12 104
99 19
37 68
103 47
50 59
61 15
31 84
3 15
45 56
18 25
87 2
99 63
72 85
38 48
89 41
74 99
8 42
78 43
15 56
33 6
52 10
27 95
31 96
17 97
101 61
82 19
46 19
1...

output:

42724

result:

ok answer is '42724'

Test #6:

score: 0
Accepted
time: 1ms
memory: 15320kb

input:

111
72 49
96 50
55 10
43 98
56 52
51 55
28 2
99 9
77 53
4 41
39 25
47 57
63 51
90 69
24 9
111 69
107 10
86 40
6 15
27 104
5 36
4 108
42 25
58 28
39 12
2 64
14 26
59 43
70 30
73 24
7 36
15 83
33 46
49 21
48 83
89 103
41 97
81 72
94 42
6 45
27 105
71 110
7 64
73 92
39 37
18 56
78 111
87 63
89 100
50 7...

output:

98530

result:

ok answer is '98530'

Test #7:

score: 0
Accepted
time: 3ms
memory: 16588kb

input:

111
82 83
52 86
21 20
16 58
29 63
110 74
33 54
3 60
59 45
16 42
49 11
58 39
40 10
52 12
108 75
25 74
76 26
58 49
56 47
4 58
100 64
76 70
15 71
57 16
53 70
78 13
34 12
5 27
110 22
58 7
30 34
70 71
93 52
75 54
79 12
2 15
42 77
14 58
107 66
14 27
55 65
92 50
101 69
83 9
79 67
102 43
43 74
76 48
19 96
8...

output:

55834

result:

ok answer is '55834'

Test #8:

score: 0
Accepted
time: 109ms
memory: 28040kb

input:

200000
183176 151527
117719 142772
169948 144229
184172 28756
101378 18789
111372 197168
24501 135561
81654 184238
177873 158588
53882 138977
84123 131028
37914 82098
158806 128577
47010 65497
61528 11435
163226 171005
142434 121859
35604 38210
185868 151406
180733 54155
131487 87823
127783 176522
1...

output:

1333333333300000

result:

ok answer is '1333333333300000'

Test #9:

score: 0
Accepted
time: 60ms
memory: 25180kb

input:

199999
69737 175098
13638 175098
175098 162487
175098 167265
97178 175098
175098 85704
175098 35740
120969 175098
175098 60701
175098 138644
175098 72055
199371 175098
66830 175098
147152 175098
175098 106468
175098 131682
175098 14672
193240 175098
30578 175098
175098 145276
175098 60830
72972 1750...

output:

39999200004

result:

ok answer is '39999200004'

Test #10:

score: 0
Accepted
time: 33ms
memory: 20260kb

input:

100000
7715 53185
90698 87475
36158 68525
73793 39869
42693 7954
78280 72429
74412 41889
23745 61260
6004 96382
42051 94491
64819 50119
50055 64296
72053 95441
78693 44001
52695 83169
75285 41640
55819 62786
80498 83710
59862 78836
72071 37134
99920 39225
53946 21212
43047 6684
87516 82823
62740 428...

output:

106160915993

result:

ok answer is '106160915993'

Test #11:

score: 0
Accepted
time: 52ms
memory: 23252kb

input:

150000
44013 24759
84022 139256
70535 124706
137512 7449
40258 112581
28536 125341
106832 105858
4 73566
111328 45319
51973 129782
67857 105750
130922 113404
133348 46233
120720 133168
49182 148612
30539 3575
14466 132130
144951 111765
15981 10905
44163 139804
46434 31319
11374 53694
41286 11361
126...

output:

232928419586

result:

ok answer is '232928419586'

Test #12:

score: 0
Accepted
time: 97ms
memory: 24428kb

input:

200000
123714 51257
195845 104455
112242 51173
91295 96034
71219 163626
166883 29504
164362 141688
172981 95838
4313 64889
9705 144828
129006 60526
30348 9439
44934 35277
56528 199461
92782 59333
66572 35716
152368 189464
43273 129849
109144 158
391 160085
24228 21988
171074 57188
3467 22623
130096 ...

output:

428654297468

result:

ok answer is '428654297468'

Test #13:

score: 0
Accepted
time: 33ms
memory: 21748kb

input:

100000
47141 75331
16770 6764
80353 19836
32204 51639
4024 35594
24687 12283
48500 3451
73715 99668
44436 83347
43231 53054
87311 57525
27574 31215
18712 69363
31342 68226
36353 13248
41635 18560
89399 20940
45981 53099
71220 63829
5636 97110
77086 89261
92828 22441
88520 32770
44358 300
32649 13579...

output:

2930473698701

result:

ok answer is '2930473698701'

Test #14:

score: 0
Accepted
time: 72ms
memory: 22112kb

input:

150000
3238 124991
61025 89005
101046 108347
138684 17525
95239 141107
4265 47113
37445 53279
61021 33055
80030 111700
2708 53147
56007 62887
12290 105303
94471 24128
102239 136524
147764 10600
38188 80169
81147 87019
23537 102026
24444 32988
13052 57750
51519 10582
45659 739
72992 31969
111349 1480...

output:

12322402308768

result:

ok answer is '12322402308768'

Test #15:

score: 0
Accepted
time: 109ms
memory: 24988kb

input:

200000
145803 189562
140495 123280
129810 57157
60389 30864
157414 175327
12840 96770
163772 95103
119480 9398
19869 153625
9884 183759
100604 41091
67101 94886
188587 101365
69961 77441
51582 55348
69512 78040
45385 107605
70342 90224
101382 125622
43405 7078
8756 53966
182494 159469
176886 61334
1...

output:

16533895307393

result:

ok answer is '16533895307393'

Test #16:

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

input:

100000
58558 37768
62749 50135
5704 57325
47093 75600
72861 18746
57082 15234
6605 81604
58821 99158
74241 27359
64259 89874
10034 67038
47001 90574
93439 59913
82672 50795
60158 2360
30670 43885
98210 86530
45900 2215
48594 9874
15075 63481
19413 44413
74255 6701
14307 32721
21569 10381
28568 51292...

output:

1257863367304

result:

ok answer is '1257863367304'

Test #17:

score: 0
Accepted
time: 74ms
memory: 23108kb

input:

150000
19452 89729
12084 69133
144361 117675
108310 130518
52885 44065
104190 156
35288 3859
51603 85385
148296 10
141537 134316
51431 138138
46705 113028
128600 94716
63721 60167
98461 50096
47158 69182
139218 126579
52676 87109
62847 118787
142255 68624
88870 61099
108207 128859
20082 48235
8179 1...

output:

4654328180123

result:

ok answer is '4654328180123'

Test #18:

score: 0
Accepted
time: 91ms
memory: 25016kb

input:

200000
153703 176423
97759 16254
177289 110601
158229 126770
134315 51492
117562 133628
179066 184577
177532 185305
49743 121120
96835 178279
154157 31962
108603 161990
129242 167650
134924 45539
20490 27057
8163 120565
136832 8936
45432 123664
46569 186980
6546 165389
134404 162646
97963 193912
114...

output:

7862840816243

result:

ok answer is '7862840816243'