QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#276749#4159. 消耗战SoyTony100 ✓251ms60736kbC++145.2kb2023-12-06 10:17:142023-12-06 10:17:14

Judging History

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

  • [2023-12-06 10:17:14]
  • 评测
  • 测评结果:100
  • 用时:251ms
  • 内存:60736kb
  • [2023-12-06 10:17:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=25e4+10;
const int maxm=2e6+10;
inline int read(){
    int x=0,w=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*w;
}
int n,m;
struct Tree{
    struct edge{
        int v,w;
        edge()=default;
        edge(int v_,int w_):v(v_),w(w_){}
    };
    vector<edge> E[maxn];
    inline void add_edge(int u,int v,int w){
        E[u].push_back(edge(v,w));
    }
    int fa[maxn],dep[maxn],siz[maxn],son[maxn];
    int dfn[maxn],dfncnt,top[maxn];
    int mn[maxn][18];
    void dfs1(int u,int f,int d){
        fa[u]=f,dep[u]=d,siz[u]=1;
        int maxson=-1;
        for(edge e:E[u]){
            int v=e.v,w=e.w;
            if(v==f) continue;
            dfs1(v,u,d+1);
            siz[u]+=siz[v];
            if(siz[v]>maxson) son[u]=v,maxson=siz[v];
        }
    }
    void dfs2(int u,int t){
        dfn[u]=++dfncnt,top[u]=t;
        if(!son[u]) return;
        dfs2(son[u],t);
        for(edge e:E[u]){
            int v=e.v;
            if(v==fa[u]||v==son[u]) continue;
            dfs2(v,v);
        }
    }
    void dfs3(int u){
        for(edge e:E[u]){
            int v=e.v,w=e.w;
            if(v==fa[u]) continue;
            mn[dfn[v]][0]=w;
            dfs3(v);
        }
    }
    inline void build_mn(){
        mn[1][0]=0x3f3f3f3f;
        dfs3(1);
        for(int k=1;k<=17;++k){
            for(int i=1;i+(1<<k)-1<=n;++i){
                mn[i][k]=min(mn[i][k-1],mn[i+(1<<k-1)][k-1]);
            }
        }
    }
    inline int query_mn(int l,int r){
        int k=log2(r-l+1);
        return min(mn[l][k],mn[r-(1<<k)+1][k]);
    }
    inline int get_LCA(int u,int v){
        while(top[u]!=top[v]){
            if(dep[top[u]]>dep[top[v]]) swap(u,v);
            v=fa[top[v]];
        }
        if(dep[u]>dep[v]) swap(u,v);
        return u;
    }
    inline int get_mn(int u,int v){
        int res=0x3f3f3f3f;
        while(top[u]!=top[v]){
            if(dep[top[u]]>dep[top[v]]) swap(u,v);
            res=min(res,query_mn(dfn[top[v]],dfn[v]));
            v=fa[top[v]];
            //printf("uv:%d %d %d\n",u,v,res);
        }
        if(dep[u]>dep[v]) swap(u,v);
        if(u!=v) res=min(res,query_mn(dfn[u]+1,dfn[v]));
        return res;
    }
    int id[maxn];
    bool mark[maxn];
    int st[maxn],tp;
    struct EDGE{
        int to,w,nxt;
    }e[maxm];
    int head[maxn],cnt;
    inline void add_EDGE(int u,int v,int w){
        e[++cnt].to=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt;
    }
    inline void build(){
        tp=0,st[++tp]=1,st[++tp]=id[1];
        head[1]=head[id[1]]=0;
        for(int i=2;i<=id[0];++i){
            int u=id[i];
            //找到第一个次栈顶深度小于等于LCA的
            //printf("%d %d %d %d\n",u,st[tp],get_LCA(u,st[tp]),st[tp-1]);
            if(get_LCA(u,st[tp])==st[tp]){
                st[++tp]=u;
                head[u]=0;
                continue;
            }
            while(tp>1&&dep[get_LCA(u,st[tp])]<dep[st[tp-1]]){
                add_EDGE(st[tp-1],st[tp],get_mn(st[tp-1],st[tp]));
                //printf("%d %d %d\n",st[tp-1],st[tp],get_mn(st[tp-1],st[tp]));
                --tp;
            }
            //LCA已然入栈
            if(get_LCA(u,st[tp])==st[tp-1]){
                head[u]=0;
                add_EDGE(st[tp-1],st[tp],get_mn(st[tp-1],st[tp]));
                //printf("%d %d %d\n",st[tp-1],st[tp],get_mn(st[tp-1],st[tp]));
                st[tp]=u;
            }
            else{
                int lca=get_LCA(u,st[tp]);
                head[lca]=0,head[u]=0;
                add_EDGE(lca,st[tp],get_mn(lca,st[tp]));
                //printf("%d %d %d\n",lca,st[tp],get_mn(lca,st[tp]));
                st[tp]=lca,st[++tp]=u;
            }
            /*for(int i=head[1];i;i=e[i].nxt) printf("%d ",e[i].to);
            printf("\n");*/
        }
        while(tp>1){
            add_EDGE(st[tp-1],st[tp],get_mn(st[tp-1],st[tp]));
            //printf("%d %d %d\n",st[tp-1],st[tp],get_mn(st[tp-1],st[tp]));
            --tp;
        }
    }
    ll dp[maxn];
    void dfs(int u){
        dp[u]=0;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to,w=e[i].w;
            //printf("%d->%d %d\n",u,v,w);
            dfs(v);
            if(mark[v]) dp[u]+=w;
            else dp[u]+=min(dp[v],(ll)w);
        }
    }
    inline void solve(){
        id[0]=read();
        for(int i=1;i<=id[0];++i) mark[id[i]=read()]=1;
        sort(id+1,id+id[0]+1,[&](int x,int y){
            return dfn[x]<dfn[y];
        });
        build();
        dfs(1);
        printf("%lld\n",dp[1]);
        for(int i=1;i<=id[0];++i) mark[id[i]]=0;
    }
}T;
int main(){
    n=read();
    for(int i=1;i<n;++i){
        int u=read(),v=read(),w=read();
        T.add_edge(u,v,w);
        T.add_edge(v,u,w);
    }
    T.dfs1(1,0,0);
    T.dfs2(1,1);
    T.build_mn();
    /*for(int i=1;i<=n;++i){
        printf("u:%d dfn:%d top:%d\n",i,T.dfn[i],T.top[i]);
    }*/
    m=read();
    while(m--){
        T.solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

100
1 2 3872
2 3 2287
2 4 2427
2 5 7759
1 6 2695
5 7 9472
6 8 1299
1 9 4637
8 10 2386
4 11 4623
10 12 5610
5 13 891
2 14 143
5 15 3363
14 16 3490
1 17 6588
14 18 2877
13 19 68
3 20 1702
17 21 700
21 22 5439
11 23 7487
22 24 2996
13 25 8201
23 26 7510
23 27 2657
26 28 5831
5 29 9863
16 30 8873
2 31 9...

output:

7267
3444
3872
727
6191
10128
7267
6191
3872
3747
5992
3011
143
2427
3872
10508
4892
5171
5171
569
6567
6567
3498
5171
6567
10828
5491
3872
3872
4572
5740
9650
8988
4192
3872
3039
1997
700
10460
2190
6887
5171
1139
9398
3726
8290
1087
6060
4693
6567
10460
7267
874
5171
4572
6046
6887
3872
3363
4161
...

result:

ok 100 lines

Test #2:

score: 10
Accepted
time: 37ms
memory: 25428kb

input:

1000
1 2 537
1 3 2059
1 4 8586
3 5 5724
3 6 8019
1 7 6286
1 8 3653
2 9 3684
4 10 6654
4 11 4488
4 12 7127
11 13 2066
11 14 7876
5 15 6664
8 16 8598
14 17 5744
15 18 3807
1 19 1351
19 20 662
13 21 3559
13 22 7508
2 23 3181
7 24 2384
21 25 3849
13 26 618
11 27 5810
24 28 4856
7 29 6843
21 30 4627
5 31...

output:

2728
2910
3824
2431
4459
7429
4827
1519
2431
3166
4339
4016
3042
5086
4125
2803
1502
2587
1920
1567
769
684
999
2575
2909
1677
1756
1155
792
2066
4020
4506
2222
363
1280
3672
3325
2728
662
1280
900
379
2106
4016
2129
4634
707
2721
2929
1849
4315
1280
848
2685
2059
2603
1406
618
4432
2544
1908
2596
1...

result:

ok 166666 lines

Test #3:

score: 10
Accepted
time: 47ms
memory: 26488kb

input:

1000
1 2 2564
1 3 1499
1 4 9826
2 5 5515
1 6 8014
2 7 638
1 8 3916
6 9 1976
3 10 8803
5 11 5933
10 12 3738
11 13 3448
10 14 9249
10 15 867
3 16 1237
8 17 3322
5 18 1794
1 19 7298
9 20 9216
9 21 3952
8 22 5296
1 23 9836
18 24 9160
2 25 6225
7 26 4424
5 27 3818
9 28 2152
4 29 6383
27 30 1505
13 31 413...

output:

2564
113
2485
501
2799
2757
5691
1499
2211
3844
4190
2901
1530
726
2564
5229
5536
2813
2743
857
2776
638
1587
2169
3519
10299
3143
1195
1961
2564
2137
2564
5275
2564
2711
1107
1555
8301
829
1772
6884
3671
2137
3770
2564
2564
1680
3801
313
3113
1496
2933
3671
2564
1910
5554
4063
2477
3083
4063
3221
3...

result:

ok 250000 lines

Test #4:

score: 10
Accepted
time: 217ms
memory: 60736kb

input:

250000
1 2 2268
1 3 3908
3 4 8278
4 5 4693
4 6 3931
5 7 2207
4 8 9819
7 9 2678
1 10 2206
3 11 433
2 12 7081
4 13 179
2 14 3770
13 15 1328
4 16 1167
10 17 3542
2 18 6968
9 19 5150
12 20 692
14 21 6096
4 22 4619
22 23 3564
23 24 801
6 25 4668
25 26 3824
18 27 3190
8 28 3064
17 29 1159
20 30 4957
23 31...

output:

11933
20150
13672
10226
9037
12030
14820
12212
11170
8490
14559
12157
12598
20332
12625
19691
13141
11319
13118
10386
11224
12343
10561
13672
13006
8748
13672
13672
11381
9626
8403
13672
10155
19619
13068
11782
11067
15861
9402
13672
13672
12118
15496
9158
12625
11842
19339
11284
8710
13653
9368
136...

result:

ok 5000 lines

Test #5:

score: 10
Accepted
time: 251ms
memory: 58744kb

input:

250000
1 2 6901
1 3 6877
3 4 4119
4 5 8363
1 6 9998
3 7 6589
3 8 9451
4 9 2328
1 10 1612
7 11 6154
8 12 1583
3 13 6664
7 14 924
8 15 9077
15 16 9191
11 17 1997
7 18 1879
13 19 9237
2 20 1222
19 21 6336
7 22 8576
12 23 8169
16 24 4638
1 25 8765
19 26 4484
11 27 6850
9 28 2985
20 29 657
29 30 4817
9 3...

output:

22470
16304
14462
11066
13700
13826
15177
11114
8911
14623
12886
16744
12731
8553
19666
13797
14211
12747
10918
11989
12280
10424
18039
8931
15555
17003
12569
17133
14638
11317
11180
10622
14142
10475
9214
22966
8192
11779
13180
10206
12513
10714
14555
13952
16398
18370
19955
20313
17191
10625
11110...

result:

ok 16666 lines

Test #6:

score: 10
Accepted
time: 196ms
memory: 58908kb

input:

250000
38777 108274 87589
108274 160854 77640
160854 60552 78805
60552 200039 58017
200039 84497 69330
84497 124673 34582
124673 58879 30083
58879 212671 64495
212671 36027 38890
36027 101232 26550
101232 191826 77803
191826 86159 43383
86159 10737 29218
10737 169665 79625
169665 215204 9275
215204 ...

output:

694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
437
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
694
...

result:

ok 9891 lines

Test #7:

score: 10
Accepted
time: 196ms
memory: 57456kb

input:

250000
28712 5893 24269
5893 234660 76106
234660 68804 34449
68804 92158 10190
92158 30430 94629
30430 147323 97917
147323 3900 76522
3900 163904 33184
163904 230315 6988
230315 84092 49596
84092 228686 22214
228686 34943 64054
34943 156088 9160
156088 40788 8540
40788 214979 48213
214979 90403 7986...

output:

531
531
531
531
531
531
531
531
531
361
531
531
531
531
531
531
531
531
531
531
531
481
531
531
531
531
531
531
438
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
531
...

result:

ok 62334 lines

Test #8:

score: 10
Accepted
time: 247ms
memory: 57964kb

input:

250000
1 2 3705
2 3 3084
3 4 8957
3 5 5735
1 6 1597
6 7 3523
5 8 1769
7 9 8021
8 10 8743
5 11 3445
9 12 2611
4 13 5966
11 14 4466
4 15 830
7 16 6111
7 17 9587
11 18 2402
2 19 178
15 20 5660
16 21 5340
9 22 4499
7 23 65
14 24 1874
16 25 3921
17 26 1203
22 27 8893
27 28 9215
4 29 4481
1 30 5282
14 31 ...

output:

5913
5302
4681
4647
6272
6725
8785
4681
3437
4347
4681
4851
4681
4184
4681
5302
4849
6116
1930
5393
5616
5959
4840
5385
4681
4681
4681
4681
5381
4853
5033
4049
4082
5302
5497
4681
2817
4332
6277
8364
3349
7342
4737
4176
4859
5854
4646
5912
6167
4859
5555
7050
5097
4711
8206
9405
4112
5075
5521
4681
...

result:

ok 50000 lines

Test #9:

score: 10
Accepted
time: 147ms
memory: 52864kb

input:

250000
1 156736 100000
156736 146447 100000
146447 238841 100000
1 91578 100000
1 181978 100000
1 248425 100000
1 134840 100000
134840 230020 100000
230020 245935 100000
1 218596 100000
218596 139329 100000
1 130973 100000
130973 155892 100000
1 44564 100000
44564 40236 100000
1 123733 100000
123733...

output:

11877300000
12066100000
1128400000
3397000000
78000000
57600000
231800000
201200000
51600000
7300000
100000
600000
300000
100000

result:

ok 14 lines

Test #10:

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

input:

10
1 2 6432
2 3 9694
3 4 9714
4 5 8890
4 6 9170
1 7 6361
1 8 1627
2 9 9824
7 10 9947
5
3 4 7 2
5 7 2 10 6 3
5 3 7 4 8 10
3 3 2 10
2 6 8

output:

12793
12793
14420
12793
8059

result:

ok 5 lines