QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#430778#4699. Election CampaignDimash#20 109ms38096kbC++203.9kb2024-06-04 14:38:122024-06-04 14:38:12

Judging History

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

  • [2024-06-04 14:38:12]
  • 评测
  • 测评结果:20
  • 用时:109ms
  • 内存:38096kb
  • [2024-06-04 14:38:12]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 3e5 + 12, MOD = 1e9 + 7;

int n,timer,tin[N],tout[N];
ll dp[N][2];
vector<int> g[N];
int up[N][20];
int b = 20;
int s[N],pos[N];
void prec(int v,int pr = -1){
    s[v] = 1;
    for(int &to:g[v]) {
        if (to == pr) continue;
        prec(to, v);
        s[v] += s[to];
        if (s[to] > s[g[v].front()]) {
            swap(to, g[v].front());
        }
    }
}
int h[N],d[N],anc[N];

int _t = 1;
void prec1(int v, int pr = 0) {
    if(!h[v]){
        h[v] =v;
    }
    pos[v] = _t++;
    anc[v] = pr;
    for(int to:g[v]){
        if(to == pr) continue;
        if(to == g[v][0]){
            h[to] = h[v];
        }
        d[to] = d[v] + 1;
        prec1(to,v);
    }
}
void dfs(int v, int pr = 1) {
    tin[v] = ++timer;
    up[v][0] = pr;
    for(int i = 1;i < b;i++){
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for(int to:g[v]){
        if(to != pr){
            dfs(to,v);
        }
    }
    tout[v] = ++timer;
}
bool is(int x,int y){
    return tin[x] <= tin[y] && tout[x] >= tout[y];
}
int lca(int v,int u){
    if(is(v,u)) return v;
    if(is(u,v)) return u;
    for(int i = b - 1;i >= 0;i--){
        if(!is(up[v][i],u)){
            v = up[v][i];
        }
    }
    return up[v][0];
}
int q;
ll res =0 ;
vector<array<int, 3>> qr[N];
ll t[N * 4];
void upd(int pos,ll val,int v = 1,int tl = 1,int tr = n){
    if(tl == tr){
        t[v] = val;
    }else{
        int tm = (tl + tr) >> 1;
        if(pos <= tm) upd(pos,val,v+v,tl,tm);
        else upd(pos,val,v+v+1,tm+1,tr);
        t[v] = t[v + v] + t[v + v + 1];
    }
}
ll get(int l,int r,int v = 1,int tl = 1,int tr = n){
    if(l > r || tl > r || l > tr) return 0;
    if(tl >= l && tr <= r) return t[v];
    int tm = (tl + tr) >> 1;
    return get(l,r,v + v,tl,tm) + get(l,r,v+v+1,tm+1,tr);
}
ll get1(int v, int u) {
    if(u == -1) return 0;
    ll ans = 0;
    while (true) {
        if (d[h[v]] < d[h[u]])
            swap(v, u);
        if (h[v] == h[u]) {
            if (pos[v] > pos[u]) swap(v, u);
            ans += get(pos[v], pos[u]);
            break;
        }
        else {
            ans += get(pos[h[v]], pos[v]);
            v = anc[h[v]];
        }
    }
    return ans;
}

void calc(int v,int pr = -1) {
    for (int to: g[v]) {
        if (to == pr)continue;
        calc(to, v);
        dp[v][0] += max(dp[to][0], dp[to][1]);
    }
    for (auto [x, y, c]: qr[v]) {
        ll S = 0;
        ll T = get(v,x) + get(v,y);
        auto proc = [&](int u) {
            if (u == -1) return;
            while(u != v){
                S += get(pos[u],pos[u]);
                u = up[u][0];
                continue;
                if(is(v,h[u])){
                    S += get(pos[h[u]],pos[v]);
                    u = anc[h[u]];
                }else{
                    S += get(pos[v],pos[u]);
                    break;
                }
            }
        };
        proc(x);
        proc(y);
        dp[v][1] = max(dp[v][1], S + c + dp[v][0]);
    }
    res = max({res,dp[v][1],dp[v][0]});
    upd(pos[v],dp[v][0] - max(dp[v][0],dp[v][1]));
}
void test(){
    cin >> n;
    for(int i = 1;i <= n - 1;i++){
        int x,y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    prec(1);
    prec1(1);
    dfs(1);
    cin >> q;
    for(int i = 1;i <= q;i++){
        int x,y,c;
        cin >> x >> y >> c;
        int z = lca(x, y);
        if(z != x){
            swap(x,y);
        }
        if(x == z){
            qr[z].push_back({y,-1,c});
        }else{
            qr[z].push_back({x,y,c});
        }
    }
    calc(1);
    cout << res << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int T = 1;
//    cin >> T;
    while(T--){
        test();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

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

input:

2
1 2
1
1 2 2288

output:

2288

result:

ok single line: '2288'

Test #2:

score: 0
Accepted
time: 0ms
memory: 11892kb

input:

8
7 1
5 3
6 8
3 8
8 1
2 1
1 4
5
3 8 2053
6 8 853
5 8 5880
2 1 5625
6 8 8165

output:

13790

result:

ok single line: '13790'

Test #3:

score: 0
Accepted
time: 0ms
memory: 11836kb

input:

20
1 14
2 14
11 2
5 2
17 5
4 5
20 17
15 20
13 15
7 15
8 13
3 8
16 8
18 3
10 16
12 18
19 12
9 19
6 9
7
20 9 5830
16 5 8758
6 9 2098
3 13 7903
19 2 9058
10 6 9412
7 1 1481

output:

11482

result:

ok single line: '11482'

Test #4:

score: 0
Accepted
time: 2ms
memory: 12008kb

input:

1000
328 389
332 389
98 328
173 332
198 328
673 332
350 198
604 328
941 332
469 98
613 604
283 350
935 941
401 604
608 604
143 198
616 350
154 198
693 332
2 941
837 604
781 332
114 332
814 328
202 389
219 673
898 350
965 98
120 173
171 941
922 673
500 673
344 673
259 941
299 673
724 332
863 941
595 ...

output:

47601

result:

ok single line: '47601'

Test #5:

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

input:

100000
51971 1236
13827 68016
26578 66644
61123 44973
37160 47011
51357 42501
57945 42568
35192 75188
49218 81425
5377 49928
96688 45414
61479 27595
78624 46328
376 20674
89257 58214
76188 29457
74822 23279
59664 53900
40575 39255
6872 87460
97312 74452
45763 46090
23199 77843
85247 52990
24695 6709...

output:

17606

result:

ok single line: '17606'

Test #6:

score: 0
Accepted
time: 41ms
memory: 38052kb

input:

100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 5...

output:

23271

result:

ok single line: '23271'

Test #7:

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

input:

100000
45904 87322
85648 87322
30242 45904
46905 85648
75331 46905
33931 46905
74362 75331
36769 33931
22564 36769
61614 22564
5425 61614
57215 5425
35745 57215
48920 57215
55586 48920
5531 55586
51674 55586
78055 51674
57472 78055
62668 57472
35877 57472
54224 35877
35922 54224
27435 35922
27068 35...

output:

64310

result:

ok single line: '64310'

Test #8:

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

input:

100000
14607 64423
84125 14607
55044 64423
63748 84125
28264 55044
71045 64423
33239 71045
89708 55044
92999 14607
27495 33239
43851 64423
1931 28264
18907 28264
42048 64423
30029 84125
25683 84125
70650 14607
77401 89708
33562 84125
48727 84125
32618 14607
47445 33239
83172 89708
5423 84125
66176 1...

output:

20132

result:

ok single line: '20132'

Test #9:

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

input:

100000
31720 3864
84558 3864
70959 31720
31185 84558
70670 31185
87658 31185
40824 70670
55702 40824
1708 40824
33268 1708
16455 1708
73000 33268
93991 73000
99103 73000
43730 99103
29520 99103
20019 43730
78102 20019
51506 78102
86663 78102
85923 51506
72476 85923
88462 85923
30178 72476
80889 8846...

output:

20325

result:

ok single line: '20325'

Test #10:

score: 0
Accepted
time: 38ms
memory: 29660kb

input:

100000
53319 22285
2456 22285
91027 22285
12942 53319
75310 12942
80182 2456
69400 2456
66791 2456
17127 75310
39358 22285
19770 17127
81690 75310
43059 66791
55551 22285
8043 69400
93859 2456
32352 75310
11929 75310
6371 53319
67663 12942
36921 53319
91139 12942
17898 2456
52075 17127
30342 75310
1...

output:

20488

result:

ok single line: '20488'

Subtask #2:

score: 0
Time Limit Exceeded

Test #11:

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

input:

2
1 2
8
2 1 1
1 2 1
2 1 1
2 1 1
2 1 1
1 2 1
1 2 1
1 2 1

output:

1

result:

ok single line: '1'

Test #12:

score: 0
Accepted
time: 0ms
memory: 11772kb

input:

32
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
34
10 20 1
18 26 1
13 1 1
9 24 1
6 30 1
30 22 1
21 26 1
18 1 1
31 19 1
29 31 1
7 23 1
5 17 1
26 8 1
14 21 1
9 5 1
20 15 1
29 8 1...

output:

5

result:

ok single line: '5'

Test #13:

score: 0
Accepted
time: 4ms
memory: 11976kb

input:

1000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
...

output:

169

result:

ok single line: '169'

Test #14:

score: -5
Time Limit Exceeded

input:

100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 5...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 10
Accepted

Test #41:

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

input:

1000
199 495
692 601
467 294
711 959
363 143
156 433
191 14
323 24
430 622
27 230
819 166
738 205
141 892
814 220
105 368
888 268
960 716
371 572
113 6
740 475
14 302
683 25
701 688
296 946
92 601
567 247
85 252
753 429
495 238
529 852
272 369
783 751
573 91
341 932
410 844
883 805
56 576
508 301
96...

output:

173613

result:

ok single line: '173613'

Test #42:

score: 0
Accepted
time: 12ms
memory: 12032kb

input:

1000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
...

output:

171886

result:

ok single line: '171886'

Test #43:

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

input:

1000
413 414
917 413
313 917
622 917
75 313
530 622
364 530
859 530
392 364
312 392
340 392
445 312
549 340
891 549
477 891
495 891
827 495
122 827
70 827
18 70
556 18
362 556
426 556
863 362
560 426
275 863
998 560
427 275
50 427
527 427
802 50
858 802
604 858
403 604
447 604
231 403
135 231
52 135...

output:

1774629

result:

ok single line: '1774629'

Test #44:

score: 0
Accepted
time: 2ms
memory: 11984kb

input:

1000
704 981
447 981
329 981
781 704
320 329
783 981
293 329
769 781
653 769
758 320
371 769
957 704
174 704
515 320
396 981
843 293
914 981
578 781
956 783
390 320
344 293
212 653
412 447
40 781
506 783
441 781
639 320
632 653
223 320
778 704
865 981
331 447
698 981
501 769
883 781
767 981
616 329
...

output:

90211

result:

ok single line: '90211'

Test #45:

score: 0
Accepted
time: 4ms
memory: 12008kb

input:

1000
883 616
149 373
533 217
551 164
380 223
226 833
48 684
387 257
466 30
208 920
227 607
129 607
643 409
796 747
648 996
412 232
355 635
685 750
709 859
442 69
414 961
646 324
725 653
768 864
803 429
134 264
98 83
815 550
146 349
317 558
889 405
729 723
561 743
622 967
27 820
114 550
390 676
424 5...

output:

187496

result:

ok single line: '187496'

Test #46:

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

input:

1000
666 416
80 666
9 666
39 9
499 39
571 499
774 571
128 571
875 774
714 128
194 714
10 194
598 10
160 598
594 160
740 594
326 740
579 326
137 326
660 137
662 137
364 660
858 364
2 858
802 2
862 2
206 862
63 862
337 206
83 63
111 337
730 83
853 111
546 853
560 853
457 546
979 560
350 457
725 979
72...

output:

1865741

result:

ok single line: '1865741'

Test #47:

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

input:

1000
718 469
977 469
898 977
89 898
558 718
155 718
895 977
412 718
604 895
76 718
149 412
146 89
198 558
442 895
941 412
371 89
724 412
842 718
126 895
919 604
418 469
957 977
945 155
249 469
700 469
132 469
102 89
278 895
633 558
737 718
360 469
484 412
152 604
693 718
376 412
912 977
708 155
780 ...

output:

93130

result:

ok single line: '93130'

Test #48:

score: 0
Accepted
time: 12ms
memory: 12032kb

input:

1000
329 905
752 905
933 752
636 933
381 636
411 381
318 381
512 411
103 318
185 512
948 103
573 948
154 948
237 573
214 154
301 214
892 301
397 301
141 397
91 397
968 91
434 91
499 968
27 434
613 499
50 613
117 50
534 50
55 117
685 55
621 685
446 621
368 621
492 368
108 492
835 492
535 835
749 535
...

output:

202793

result:

ok single line: '202793'

Test #49:

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

input:

1000
402 779
39 779
930 779
851 779
901 930
668 930
862 39
301 779
200 901
902 901
608 779
375 402
940 39
797 39
994 668
667 851
916 301
705 402
617 901
576 39
758 779
569 39
938 851
77 779
105 301
892 930
514 668
45 39
681 301
9 862
146 930
171 402
472 200
245 301
122 901
647 39
98 901
790 301
54 4...

output:

98570

result:

ok single line: '98570'

Test #50:

score: 0
Accepted
time: 11ms
memory: 12044kb

input:

1000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
...

output:

217094

result:

ok single line: '217094'

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%