QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#480559#7305. Lowest Common Ancestor_LAP_AC ✓131ms20584kbC++142.4kb2024-07-16 16:34:002024-07-16 16:34:00

Judging History

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

  • [2024-07-16 16:34:00]
  • 评测
  • 测评结果:AC
  • 用时:131ms
  • 内存:20584kb
  • [2024-07-16 16:34:00]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10, M = 4e5 + 10;
int n, w[N], h[N], e[M], ne[M], idx;
inline void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++; }


int fa[N], dfn[N], siz[N], son[N], top[N], dfs_clock;
void dfs(int u, int f) {
    fa[u] = f, siz[u] = 1, son[u] = 0;
    for(int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i]; if(v == f) continue;
        dfs(v, u), siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}
void hld(int u, int topf) {
    top[u] = topf, dfn[u] = ++dfs_clock;
    if(!son[u]) return;
    hld(son[u], topf);
    for(int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i]; if(v == fa[u] || v == son[u]) continue;
        hld(v, v);
    }
}
struct Fenwick {
    long long C[N];
    Fenwick() {memset(C, 0, sizeof C); }
    inline void clear() {memset(C + 1, 0, sizeof(long long) * n); }
    inline void add(int p, int x) {for(; p <= n; p += p & -p) C[p] += x; }
    inline long long ask(int p) {long long r = 0; for(; p; p -= p & -p) r += C[p]; return r; }
    inline long long ask(int l, int r) {return ask(r) - ask(l - 1); }
    inline long long ask_subtree(int u) {return ask(dfn[u], dfn[u] + siz[u] - 1); }
} BIT, BIT2;

int f[N];

inline void solve() {
    idx = 0, dfs_clock = 0;
    memset(h + 1, -1, sizeof(int) * n);
    for(int i = 1; i <= n; i ++)
        cin >> w[i];
    for(int i = 2; i <= n; i ++) {
        int x; cin >> x;
        add(x, i), add(i, x);
    }
    dfs(1, 0), hld(1, 1);
    // for(int i = 1; i <= n; i ++)
    //     cout << top[i] << " \n"[i == n];
    for(int i = 1; i <= n; i ++) f[i] = 0;
    for(int i = 1; i <= n; i ++) {
        int u = i;
        f[i] += w[u] * BIT.ask_subtree(u), u = top[u];
        while(fa[u]) {
            f[i] += w[fa[u]] * (BIT.ask_subtree(fa[u]) - BIT.ask_subtree(u));
            u = top[fa[u]];
        }
        int lst = i;
        while(lst) {
            int now = top[lst];
            if(now != lst) f[i] += BIT2.ask(dfn[now], dfn[lst] - 1);
            lst = fa[now];
        }
        u = i;
        BIT.add(dfn[u], 1);
        while(u) {
            BIT2.add(dfn[u], w[u]);
            u = fa[top[u]];
        }
    }
    for(int i = 2; i <= n; i ++)
        cout << f[i] << '\n';
    BIT.clear(), BIT2.clear();
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    while(cin >> n) solve();

    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 16020kb

input:

3
1 2 3
1 1
5
1 2 3 4 5
1 2 2 1

output:

1
2
1
3
5
4

result:

ok 6 numbers

Test #2:

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

input:

13
887 4555 8570 5485 8611 9500 295 2499 83 4959 9772 8620 3825
4 4 1 3 7 12 2 1 9 5 8 12
16
3405 9213 9243 8188 2733 1333 1614 4907 4256 7506 4228 1286 6121 6155 4082 8084
1 12 9 4 2 13 3 8 9 7 11 15 8 1 10
5
7183 1481 9468 8242 1044
1 5 5 1
3
5758 3693 1694
1 2
20
6683 4426 5616 8166 810 4265 3000...

output:

887
6372
11857
20427
21897
22192
26895
7096
7179
47267
48895
57515
3405
6810
16053
24241
22833
15057
30886
34491
38747
37197
23773
65304
57242
55117
66877
7183
14366
15410
16454
5758
9451
6683
11109
23015
24891
29156
35244
41332
41537
37300
51071
58569
59109
70092
93562
98559
108242
88010
120021
991...

result:

ok 181926 numbers

Test #3:

score: 0
Accepted
time: 67ms
memory: 13992kb

input:

1477
3418 2604 3534 2752 131 645 5196 4830 3302 3842 1625 3740 9292 9939 1582 4155 3540 3753 7421 3629 7596 2043 1399 8955 2124 7955 6100 1346 1339 3935 767 4593 1720 3200 2248 6972 7122 9566 624 9948 6048 8338 208 8669 827 3770 4306 9503 1935 6488 454 3510 4974 2964 5407 138 5468 1142 1812 5864 803...

output:

3418
5803
9152
13820
18874
26680
33465
41014
25683
51131
42058
39772
46791
50431
71966
64478
59926
77557
63112
88734
65714
71174
94621
92142
101334
117673
92286
90454
122881
126056
126405
137417
149983
109256
150899
154398
173188
119649
166368
169452
175799
143976
216296
149549
223478
222792
195677
...

result:

ok 199907 numbers

Test #4:

score: 0
Accepted
time: 130ms
memory: 16212kb

input:

200000
8748 791 4490 1890 3323 1988 6142 9186 1748 6247 5686 247 5513 8788 3823 7152 9488 7315 6394 4878 2869 5935 395 8470 9990 7448 3034 9602 5477 8257 9605 8576 2122 418 28 2865 6223 6295 8852 6891 1554 7663 869 728 486 5102 716 1349 82 3819 4154 9380 4368 9283 7842 4298 3903 5172 6847 2578 8050 ...

output:

8748
10980
21720
23004
28494
43086
40992
43082
51656
55659
43921
65566
70999
87217
105493
115456
108075
96154
99671
108252
123219
115979
129363
128272
161386
204287
213656
166933
194923
216010
171656
177783
187699
195840
210767
207893
227214
227883
277178
282916
225885
246528
237889
342600
263596
28...

result:

ok 199999 numbers

Test #5:

score: 0
Accepted
time: 130ms
memory: 16256kb

input:

200000
1089 2052 9819 2755 1142 9026 8106 7060 4295 7566 5317 9030 3724 3949 1766 4512 1763 4073 332 5723 9306 4271 2328 4233 9127 7407 4513 8347 5088 4319 2032 8553 5123 6344 9637 9759 639 6519 6880 6282 6297 3518 6936 1102 3337 1344 8040 3603 3866 3160 5501 7044 6637 5267 2249 7855 3766 6929 8771 ...

output:

1089
3864
8375
13838
22864
24031
18902
27077
28777
32769
38870
59226
63315
44138
57381
76962
69244
103066
99786
84003
91878
92896
102809
90402
109611
141263
139331
97590
97005
167931
143972
140174
160648
142079
192737
172340
263643
220362
218229
193811
227606
187026
202919
197660
204090
125557
17460...

result:

ok 199999 numbers

Test #6:

score: 0
Accepted
time: 131ms
memory: 16216kb

input:

200000
4960 3655 2962 5492 284 8613 2140 1855 1784 3288 6928 782 6150 919 1823 6985 4922 4588 5377 5805 3711 2564 4833 2169 5376 8179 8047 3601 3712 1133 8796 1166 6115 2174 8529 4364 2418 3091 4696 8459 5931 4623 1009 8447 6431 5783 7599 7664 3939 422 9257 9003 2591 8922 5705 2079 4434 3541 2112 75...

output:

4960
9255
15548
17532
17803
30260
61048
47274
40937
44392
101419
73337
72533
89824
79311
89089
148745
105683
103274
130544
126881
116509
115470
142269
155753
229745
158378
246875
181490
184413
169628
212405
189505
203094
210912
198270
200105
227667
222435
220034
235243
207768
363235
221680
222437
26...

result:

ok 199999 numbers

Test #7:

score: 0
Accepted
time: 113ms
memory: 16252kb

input:

200000
1992 2831 3632 5028 5398 6876 265 7751 6179 4848 9158 3408 6501 8481 7845 5506 3540 5145 4729 1886 9069 9909 1721 2476 6273 2215 5296 9017 5299 2037 9947 115 3390 5335 574 6863 5133 2156 3487 132 2673 6214 7274 6014 4223 4041 1035 4507 687 5504 3863 5873 5886 9016 9027 9926 8781 9012 4683 423...

output:

1992
10357
18862
17382
19895
47777
33964
25358
48453
32678
37540
28612
3900
70418
41017
71093
72260
88771
61948
49435
86553
57151
80177
78259
93312
108210
96451
135443
16869
129070
82621
153626
122872
135908
152350
161306
134708
105506
302147
120358
153630
164305
157384
170420
189791
45980
366067
14...

result:

ok 199999 numbers

Test #8:

score: 0
Accepted
time: 99ms
memory: 16284kb

input:

200000
8169 5022 7242 4618 3683 9870 7200 3627 4997 5129 7738 8636 2362 3814 5421 9340 4098 6699 9986 4828 1970 4295 472 3029 2832 8201 543 7008 328 134 9966 6635 2793 7159 6653 8331 6025 1272 92 6676 813 6203 475 387 6146 8771 4960 7973 4727 2154 2788 5021 384 4075 5622 6082 3605 4168 9062 6078 284...

output:

8169
10197
14815
18860
22152
30279
35393
26746
39810
43539
64870
116607
76194
66942
85971
94578
101277
97119
63371
98277
137642
134935
136332
138839
158295
76220
159301
165499
177684
180953
102367
186727
64588
193451
98503
207674
243036
217050
232352
247817
254353
240046
114336
263202
229941
207891
...

result:

ok 199999 numbers

Test #9:

score: 0
Accepted
time: 87ms
memory: 16280kb

input:

200000
9520 6100 4800 3079 7421 5698 1679 4144 2153 6453 2237 7931 2269 2167 2262 2080 7769 818 8026 6126 7261 2021 6926 1621 2593 4739 7273 1274 8429 4995 2409 5687 5617 6929 4588 6152 2399 8220 9159 6815 764 9110 8163 2592 7459 6983 1994 1286 4689 2011 174 8588 7258 7215 2259 5813 2803 7783 6272 2...

output:

9520
19403
21411
25505
43628
57120
55647
74555
69285
90590
73265
101210
112650
117925
109693
121027
104698
156350
164376
45650
150924
166972
164579
54910
59151
184391
187351
214949
217765
209804
213313
164492
218867
210257
265240
277014
281680
237491
89810
290865
264382
294978
253891
89800
322344
33...

result:

ok 199999 numbers

Test #10:

score: 0
Accepted
time: 77ms
memory: 16548kb

input:

200000
5956 1121 8177 4202 1212 6833 6455 5492 4523 9183 4971 2644 7369 638 4808 5922 8514 4328 7020 7481 3511 7226 9369 4841 3067 4645 5637 9315 2615 9727 6106 720 4167 8768 7046 2235 1115 8918 5772 9282 8439 9409 2306 3625 9299 5367 9505 9926 9835 9425 2968 6598 9520 2972 2633 3639 1333 2650 5755 ...

output:

5956
7302
17868
23824
29780
33631
36948
57887
49575
72227
59094
72885
88452
74200
85796
92362
81412
109685
128791
103777
99159
175778
118766
137504
119447
115321
170889
131730
156998
138521
145241
131893
205196
156799
141462
166347
145696
163896
177935
162049
161747
170665
248569
183726
182658
15363...

result:

ok 199999 numbers

Test #11:

score: 0
Accepted
time: 68ms
memory: 17132kb

input:

200000
5900 5918 8506 1255 2047 8302 7821 8527 8050 8619 9309 6639 528 6501 5415 7562 4073 5905 3741 6359 6351 4647 5138 3855 9113 258 482 8192 9362 8547 3831 4076 538 2063 9605 4666 9924 3804 8047 6932 2503 2600 6255 9256 8942 4802 5090 5224 360 4879 3338 4617 7512 5622 8346 5015 8117 8725 3053 232...

output:

5900
14406
22456
28807
38808
46148
54931
62706
64932
66403
78855
80206
91707
88375
93790
127633
114372
117173
128768
137705
129909
134638
138073
183992
135106
115908
153402
187300
162257
197704
247856
186201
171567
220821
281060
177433
297637
193094
260984
259058
261658
280351
347143
296085
241406
2...

result:

ok 199999 numbers

Test #12:

score: 0
Accepted
time: 53ms
memory: 18364kb

input:

200000
4833 8709 6425 876 8669 5761 5485 8395 2650 2545 3447 6177 3503 2864 3769 9105 2618 1386 7387 6628 1099 2929 4102 8564 8470 5404 8666 3009 4213 2131 2041 2767 3892 5204 1354 6070 195 481 2711 3121 3512 176 6191 2352 2314 8298 4453 1446 8359 3596 6862 7835 1839 1017 7783 6202 2822 1413 7198 19...

output:

4833
11258
19967
19332
21982
35118
43513
34298
50891
55884
62061
62890
65381
70960
84496
93601
60820
62206
69593
62395
137204
71964
149887
162614
163761
169165
172174
175209
166930
181553
184320
187087
189854
192565
211903
202147
204877
206768
210709
214612
214901
220835
222014
224776
233074
233682
...

result:

ok 199999 numbers

Test #13:

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

input:

200000
7320 5235 2627 4171 2297 7220 7526 2303 3596 4368 2710 1976 1897 8915 4812 1924 7019 6686 7815 8693 2689 8852 7992 5521 4479 4238 2066 4530 4970 360 9712 8550 9712 3697 3839 4704 5838 3407 7423 9717 2520 5049 5846 9777 6708 6475 8429 1856 4543 117 8289 6405 4982 5740 1779 5494 6270 6872 8361 ...

output:

7320
12555
15182
17479
24699
22073
29599
31902
34205
36915
41283
43259
45156
54071
62986
64910
71929
79744
87559
96252
98941
107793
115785
121306
134349
138587
143117
147647
152617
152977
162689
171239
179789
183486
187325
191164
197002
204425
211848
214368
221946
226995
232044
238752
245460
253889
...

result:

ok 199999 numbers

Extra Test:

score: 0
Extra Test Passed