QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#783639#9648. 数据结构Nesraychan100 ✓2012ms472252kbC++146.5kb2024-11-26 11:08:342024-11-26 11:08:35

Judging History

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

  • [2024-11-26 11:08:35]
  • 评测
  • 测评结果:100
  • 用时:2012ms
  • 内存:472252kb
  • [2024-11-26 11:08:34]
  • 提交

answer

#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 200200
#define int long long
#define oo (1ll<<60)
IL int read()
{
    reg int x=0,f=0; reg char ch=getchar();
    while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}

const int B=3;
int n,q;
std::vector<int>G[N];

IL void add(reg int u,reg int v){G[u].push_back(v),G[v].push_back(u);}

namespace Segment
{

#define ls (o<<1)
#define rs (o<<1|1)
#define mid (l[o]+r[o]>>1)

int l[N<<2],r[N<<2],sum[N<<2],mx[N<<2],tag[N<<2];

IL int max(reg int x,reg int y){return x>y?x:y;}
IL void pushup(reg int o){sum[o]=sum[ls]+sum[rs],mx[o]=max(mx[ls],mx[rs]);}
IL void apply(reg int o,reg int k){sum[o]+=k*(r[o]-l[o]+1),mx[o]+=k,tag[o]+=k;}
IL void pushdown(reg int o){if(tag[o])apply(ls,tag[o]),apply(rs,tag[o]),tag[o]=0;}

void build(reg int o,reg int L,reg int R)
{
    l[o]=L,r[o]=R;
    if(L<R)build(ls,L,mid),build(rs,mid+1,R);
}

void modify(reg int o,reg int L,reg int R,reg int k)
{
    if(L<=l[o]&&r[o]<=R)return apply(o,k);
    if(L>r[o]||l[o]>R)return;
    pushdown(o),modify(ls,L,R,k),modify(rs,L,R,k),pushup(o);
}

int query_sum(reg int o,reg int L,reg int R)
{
    if(L<=l[o]&&r[o]<=R)return sum[o]; if(L>r[o]||l[o]>R)return 0;
    return pushdown(o),query_sum(ls,L,R)+query_sum(rs,L,R);
}

int query_max(reg int o,reg int L,reg int R)
{
    if(L<=l[o]&&r[o]<=R)return mx[o]; if(L>r[o]||l[o]>R)return -oo;
    return pushdown(o),max(query_max(ls,L,R),query_max(rs,L,R));
}

#undef ls
#undef rs
#undef mid

}

int sz[N],dep[N],fa[N],son[N],anc[N];

void dfs1(reg int u)
{
    dep[u]=dep[fa[u]]+(sz[u]=1);
    for(auto v:G[u])if(!sz[v])
    {
        fa[v]=u,dfs1(v),sz[u]+=sz[v];
        if(sz[son[u]]<sz[v])son[u]=v;
    }
}

void dfs2(reg int u,reg int top)
{
    anc[u]=top; if(son[u])dfs2(son[u],top);
    for(auto v:G[u])if(!anc[v])dfs2(v,v);
}

IL int lca(reg int x,reg int y)
{
    for(;anc[x]!=anc[y];x=fa[anc[x]])
        if(dep[anc[x]]<dep[anc[y]])std::swap(x,y);
    return dep[x]<dep[y]?x:y;
}

template<class T>IL void clear(reg T &a){T b; std::swap(a,b);}

int dfn[N],ed[N],dfc;

void dfs3(reg int u)
{
    std::vector<int>P,Q;
    for(reg int x=u;x;x=son[x])
    {
        P.push_back(x);
        if(!dfn[x])dfn[x]=++dfc;
    }
    for(reg int o=1;o<=B;++o)
    {
        clear(Q);
        for(auto u:P)for(auto v:G[u])if(v!=fa[u])
        {
            if(!dfn[v])dfn[v]=++dfc;
            Q.push_back(v);
        }
        std::swap(P,Q);
    }
    for(reg int v=u;v;v=son[v])for(auto w:G[v])
        if(w!=fa[v]&&w!=son[v])dfs3(w);
}

struct Range{int l,r;};

#define Sets std::vector<Range>

Sets work(reg Sets a)
{
    Sets b;
    std::sort(a.begin(),a.end(),[&](const Range &x,const Range &y){return x.l<y.l;});
    reg int L=0,R=-1;
    for(auto &[l,r]:a)
        if(l==R+1)R=r;
        else ~R?b.push_back({L,R}),0:0,L=l,R=r;
    if(~R)b.push_back({L,R});
    return b;
}

Sets merge(const Sets &a,const Sets &b)
{
    Sets c;
    for(auto p:a)c.push_back(p);
    for(auto p:b)c.push_back(p);
    return c;
}

IL void ins(reg Sets &a,const Sets &b)
{
    a=work(merge(a,b));
}

Sets del(const Sets &a,const Sets &b)
{
    Sets c;
    reg int l=0,r=-1,n=b.size();
    for(auto &[al,ar]:a)
    {
        while(r<n-1&&b[r+1].r<=ar)++r;
        reg int p=al,i;
        for(i=l;i<=r;++i)
        {
            if(p<b[i].l)c.push_back({p,b[i].l-1});
            p=b[i].r+1;
        }
        if(p<=ar)c.push_back({p,ar});
        l=r+1;
    }
	return work(c);
}

Sets sub[N],subk[N][4],upk[N][4],linek[N][4],pointk[N][4];

void dfs4(reg int u)
{
    sub[u].push_back({dfn[u],dfn[u]});
    subk[u][0]=sub[u];
    for(auto v:G[u])if(v!=fa[u])
    {
        dfs4(v),ins(sub[u],sub[v]),upk[v][0].push_back({dfn[u],dfn[u]});
        for(reg int i=1;i<=B;++i)ins(subk[u][i],subk[v][i-1]);
    }
    Sets tmp[4];
    std::vector<int>P;
    for(auto v:G[u])if(v!=fa[u])P.push_back(v);
    for(reg int i=0;i<=B;++i)tmp[i].clear();
    for(auto v:P)for(reg int i=1;i<=B;++i)
        ins(upk[v][i],tmp[i]),ins(tmp[i],subk[v][i-1]);
    std::reverse(P.begin(),P.end());
    for(reg int i=0;i<=B;++i)tmp[i].clear();
    for(auto v:P)for(reg int i=1;i<=B;++i)
        ins(upk[v][i],tmp[i]),ins(tmp[i],subk[v][i-1]);
}

void dfs5(reg int u)
{
    for(reg int i=0;i<=B;++i)linek[u][i]=subk[u][i];
    for(reg int i=0;i<=B;++i)ins(linek[u][i],linek[fa[u]][i]);
    for(reg int i=0,j,v;i<=B;++i)
    {
        pointk[u][i]=subk[u][i];
        for(j=1,v=u;j<=i&&v;++j,v=fa[v])
            ins(pointk[u][i],upk[v][i-j]);
    }
    for(reg int i=1;i<=B;++i)ins(pointk[u][i],pointk[u][i-1]);
    for(auto v:G[u])if(v!=fa[u])dfs5(v);
}

Sets split(reg int x,reg int y,reg int k)
{
    reg int z=lca(x,y);
    return work(merge(pointk[z][k],merge(del(linek[x][k],linek[z][k]),del(linek[y][k],linek[z][k]))));
}

IL void cmax(reg int &x,reg int y){x<y?x=y:0;}

main()
{
    n=read(),q=read();
    for(reg int i=1;i<n;++i)add(read(),read());
    Segment::build(1,1,n);
    dfs1(1),dfs2(1,1),dfs3(1),dfs4(1),dfs5(1);
    for(reg int op,x,y,k,w;q--;)
    {
        op=read(),x=read();
        if(op==1)
        {
            y=read(),k=read(),w=read();
            auto P=split(x,y,k);
            for(auto &[l,r]:P)
                Segment::modify(1,l,r,w);
        }else if(op==2)
        {
            w=read();
            auto P=sub[x];
            for(auto &[l,r]:sub[x])
                Segment::modify(1,l,r,w);
        }else if(op==3)
        {
            y=read(),k=read();
            auto P=split(x,y,k);
            reg int res=0;
            for(auto &[l,r]:P)
                res+=Segment::query_sum(1,l,r);
            printf("%lld\n",res);
        }else if(op==4)
        {
            auto P=sub[x];
            reg int res=0;
            for(auto &[l,r]:P)
                res+=Segment::query_sum(1,l,r);
            printf("%lld\n",res);            
        }else if(op==5)
        {
            y=read(),k=read();
            auto P=split(x,y,k);
            reg int res=-oo;
            for(auto &[l,r]:P)
                cmax(res,Segment::query_max(1,l,r));
            printf("%lld\n",res);
        }else
        {
            auto P=sub[x];
            reg int res=-oo;
            for(auto &[l,r]:P)
                cmax(res,Segment::query_max(1,l,r));
            printf("%lld\n",res);
        }
    }
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 1715ms
memory: 462952kb

input:

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

output:

0
62518
0
245795
0
88508
0
90022
0
0
362082
0
166057
0
-263428
27453
0
0
0
0
-149830
0
0
0
-82026
-342853
0
-325561
0
0
0
0
-372644
0
-174422
-309086
-558744
0
0
0
0
0
0
0
294312
-779200
0
-57599
-266309
0
-266309
-668682
0
0
0
0
-420482
0
-437910
0
-145971
0
1361331
0
0
0
89268
0
0
0
-342838
-11323...

result:

ok 99962 numbers

Test #2:

score: 10
Accepted
time: 1103ms
memory: 316016kb

input:

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

output:

-693174644
-407448312
0
-218765316
-2646366679
-2706177783
-118075560
-688361945
-5326629756
-1034523241
248255
49651
397583533
-675507964
536236
-35250078
0
84875564
3666050542
1641758589
19873128850
278324
6513679386
278324
49896394094
3479173830
1135068121
4643542916
1714703106
348608
207206572
3...

result:

ok 100230 numbers

Subtask #2:

score: 10
Accepted

Test #3:

score: 10
Accepted
time: 1676ms
memory: 462504kb

input:

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

output:

0
0
0
0
0
0
0
-104272
107152
1440
0
-154968
53576
0
-558956
-105074
0
0
1693
0
0
-351850
0
0
0
0
-148344
0
0
0
0
0
-336768
0
-242877
-239540
-177269
0
0
0
-713232
0
0
0
0
-361599
13257
0
13257
0
0
-34188
0
53229
-434587
0
0
0
0
81294
0
0
0
0
0
97819
66486
0
53229
-294743
-355594
0
0
0
-10356
66486
4...

result:

ok 133269 numbers

Test #4:

score: 10
Accepted
time: 1091ms
memory: 317800kb

input:

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

output:

0
0
0
0
0
-1710891717
0
35204
0
91771
0
0
0
91771
-441533729
0
0
0
-1655012194
0
0
-1222376926
-644402193
-211228869
0
0
-1354117733
0
-1373876471
0
0
-1155789170
61132
0
-464974584
91771
0
0
12505
145145
0
8782729811
168854
1238148306
124865
1098321605
137370
7233827198
1894745981
137370
1064541891...

result:

ok 133442 numbers

Subtask #3:

score: 10
Accepted

Test #5:

score: 10
Accepted
time: 1236ms
memory: 445668kb

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
89044
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
535446
0
0
0
0
0...

result:

ok 99913 numbers

Test #6:

score: 10
Accepted
time: 919ms
memory: 315964kb

input:

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

output:

0
63908
207701
15977
522576
15977
143793
152018
15977
0
36756
78843
36756
0
315372
10052804992
20779
78843
0
36756
36756
7665373505
62337
23361399106
3187120
62337
3742676532
546438
147024
103895
0
7880424170
253252
272541
449350
4081653
453517
314628
2267585
361886
18098891585
1438437
633130
449350...

result:

ok 99917 numbers

Subtask #4:

score: 10
Accepted

Test #7:

score: 10
Accepted
time: 1260ms
memory: 458540kb

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 133520 numbers

Test #8:

score: 10
Accepted
time: 938ms
memory: 318296kb

input:

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

output:

0
81278
0
63687
63687
63687
63687
63687
63687
63687
63687
63687
63687
636870
63687
63687
144965
11254124900
636870
63687
144965
144965
63687
0
63687
63687
63687
4947438975
509496
318435
114304
63687
0
63687
105584
63687
0
16280833342
1009002621
105584
246008
105584
260692
105584
316752
311309
117234...

result:

ok 133481 numbers

Subtask #5:

score: 10
Accepted

Test #9:

score: 10
Accepted
time: 1708ms
memory: 470008kb

input:

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

output:

1857150
-106797
0
0
64612
0
1808864
0
1319630
0
13621832
1227363
15607376
2151610
4909784
2647098
1470564
0
-2570850
0
14130724
0
7145118
0
31967983
0
-639181
0
27143144
0
12122816
166580
0
0
-2801375
0
11387471
22813486
0
6006168
0
0
0
23241781
12394024
0
13950003
8070072
19017220
0
21145621
0
1431...

result:

ok 99967 numbers

Test #10:

score: 10
Accepted
time: 1120ms
memory: 316108kb

input:

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

output:

0
0
5843630
20392960
0
0
-903453097
-179420161
0
0
-1330737
0
-1154278269
-37153603
0
0
-2537810064
-5318685886
-1097999168
401558225
2883316
-3765521921
1544718973
124390
4918819215
5870207005
809430858
392406
12414884357
124390
112222
9272513996
0
62195
81431
124390
995995782
112222
985671590
1104...

result:

ok 99987 numbers

Test #11:

score: 10
Accepted
time: 1732ms
memory: 463464kb

input:

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

output:

0
0
0
0
741068
0
3258310
0
6427499
0
7251389
5580113
1622608
0
0
0
0
-2321847
0
-734707
-573220
-200140
1025755
0
0
3491849
0
7656367
0
9631224
0
0
7418639
7978399
12217526
0
8036158
0
0
9101393
8775461
7083137
0
0
0
10929162
0
8463857
9434348
0
6285986
0
20776
7479344
0
4953795
7221567
0
0
6522229
...

result:

ok 100056 numbers

Test #12:

score: 10
Accepted
time: 1114ms
memory: 318024kb

input:

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

output:

0
0
-1169809800
-1954619812
0
0
-3133767676
0
0
0
-4575579696
-4575619294
-452469552
-4128734151
-4575579696
0
-608229548
-752126234
-3561029056
-242136724
-2984947836
-3540290054
-834247804
-3880852457
23212
0
512821584
2084796550
8600974617
1649594022
2832246307
641597529
-1214351503
312129
330840...

result:

ok 100178 numbers

Subtask #6:

score: 10
Accepted

Test #13:

score: 10
Accepted
time: 1650ms
memory: 447944kb

input:

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

output:

0
0
0
0
0
0
0
0
0
-597754
0
0
0
113310
258283
0
0
6434569
0
258283
0
0
7749214
8481184
258283
197065
5494216
0
13981043
0
0
0
0
0
0
0
0
3224810
0
6758948
0
8832084
0
282018
14877927
0
418806
0
0
0
379295
0
-448225
0
340187
0
0
340187
0
340187
0
9742771
10496602
17197688
0
234958
0
234958
340187
1280...

result:

ok 132677 numbers

Test #14:

score: 10
Accepted
time: 1062ms
memory: 314060kb

input:

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

output:

0
74311326
147063
1062566318
25407
680607564
49021
49021
1598679355
-30708
147063
13552
-4727124378
98042
-1568058708
-4778331532
85148
-687534891
-7431
-7722399495
-2730026187
49021
85148
85148
49021
-116193
-4290439791
98042
-3726928035
106905
33565
113952
92528
160327
92528
16107343084
92528
1574...

result:

ok 133109 numbers

Test #15:

score: 10
Accepted
time: 1739ms
memory: 461644kb

input:

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

output:

0
0
0
-16674
21458
0
21458
21458
0
213082
0
0
213082
0
0
-148606
0
0
-235294
21458
0
0
0
21458
0
0
-8244269
0
-6782319
0
-3467950
-2367692
0
0
0
0
0
0
0
-5553757
0
0
0
0
-2430091
0
0
34967
0
-1204224
0
0
88102
0
0
0
0
-3127007
0
28352
37482
0
-4041681
1625143
0
163566
163370
0
0
98293
1612691
0
1088...

result:

ok 132943 numbers

Test #16:

score: 10
Accepted
time: 975ms
memory: 317808kb

input:

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

output:

9688739692
8225700308
1607557809
173891
200931
15599260152
3802616612
181827
181827
5167631749
97070
97070
253694
9115995013
294662
97070
107947
6082228176
160280980
970096010
11827007855
317407
170647
15021902631
27377495948
133202
144079
259808
6861431973
133202
80586
318637
318637
22387170721
115...

result:

ok 133078 numbers

Subtask #7:

score: 20
Accepted

Dependency #1:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #5:

100%
Accepted

Test #17:

score: 20
Accepted
time: 1971ms
memory: 472252kb

input:

199999 200000
92220 2
36934 3
51657 4
135444 5
21288 6
141433 7
4593 8
131850 9
153432 10
168339 11
63376 12
35986 13
34388 14
24670 15
29090 16
148010 17
7931 18
63638 19
196107 20
8922 21
79020 22
143708 23
120639 24
191727 25
5871 26
139983 27
161665 28
77131 29
123179 30
57165 31
102267 32
15530...

output:

0
0
23450704
0
112690608
41597768
159732
0
0
8575137
-19657343
0
29923114
3341804
0
0
93803875
291310
-302055
29818547
346256
0
0
35631
7265769
249917608
0
0
0
0
61405401
0
148201331
28792946
259676501
16361595
0
0
0
6320250
3267155
24492071
0
0
90546087
0
0
-6733673
0
-59528691
119098630
112016321
...

result:

ok 100142 numbers

Test #18:

score: 20
Accepted
time: 1859ms
memory: 453948kb

input:

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

output:

0
0
0
0
0
0
898309
248883
2470956
3676987
0
51539
0
0
1337234
0
5790736
20615407
46566394
0
28434589
0
0
0
1277284
68917680
0
32798490
10296671
1183162
46676816
0
0
41375228
108808759
134481871
0
118883831
64424045
0
0
10442662
0
20880896
0
51986202
0
0
1623287
40530292
0
174760
0
11487480
0
0
43634...

result:

ok 100108 numbers

Test #19:

score: 20
Accepted
time: 404ms
memory: 198768kb

input:

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

output:

0
0
0
185169489
926
-12258630511
-12258630511
-30991955534
-583406
-174657
-174657
-174657
-34931278744
-174657
-5153
-3084073250
-3084073250
-3084023657
-10538623657
-10538623657
-52696
-10538443193
-52696
-52696
-52696
-76011
-7217713995
-36093
-9202513995
-9202456805
-46017
-9202374741
-46017
717...

result:

ok 99879 numbers

Test #20:

score: 20
Accepted
time: 595ms
memory: 283900kb

input:

200000 199999
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 ...

output:

12629705684
11679257152
15713347201
1302608494
19632100694
7276215232
10194079554
3858018698
3059904493
3855625522
8236486648
4538007629
1551237292
43613248920
12583190871
12274073913
52805982632
11025728883
58713722200
5937454429
27475709888
8300421792
13501063858
70340460041
90183575579
4035306786...

result:

ok 100093 numbers

Test #21:

score: 20
Accepted
time: 1158ms
memory: 315876kb

input:

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

output:

0
1178679222
3117876104
3889886904
13410491784
1999469690
1458460165
2766558087
3713269936
295982
10070574266
2610353565
9787136988
732621
5004825424
-1178910677
-3705294717
-1972680028
-494606533
295982
1709449
-1379598654
225573
295982
147991
488414
-2210903139
471479
-1568067926
353187390
2144000...

result:

ok 99847 numbers

Test #22:

score: 20
Accepted
time: 2012ms
memory: 469384kb

input:

200000 200000
42975 2
114618 3
124461 4
39595 5
57834 6
23697 7
128076 8
20035 9
139066 10
130369 11
9921 12
130463 13
181357 14
148102 15
39879 16
183168 17
167851 18
23361 19
55165 20
163848 21
50457 22
70458 23
5324 24
160897 25
67889 26
11875 27
112890 28
144650 29
61584 30
129522 31
144568 32
6...

output:

0
-15984149
0
-29078715
-10461022
0
0
0
-64911884
-9041121
0
0
-26588336
0
-2418358
-4012055
0
-15855738
0
-3548670
-12444959
2192937
0
0
0
-28389970
0
0
0
13538240
0
-51152702
48462219
156437
-23428247
-7148142
0
0
-6030947
91781703
0
-27566905
0
-36775793
0
59442135
17598660
0
-73311238
8718008
0
...

result:

ok 99917 numbers

Test #23:

score: 20
Accepted
time: 1871ms
memory: 458416kb

input:

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

output:

0
652032
102314688
0
21082368
4238208
0
15110085
0
68767779
0
0
21615252
6346836
0
-177804
-13176911
0
0
2188735
28863642
0
0
344100
-1372765
0
0
0
4483592
0
28416
619707
546116
71954319
0
0
-333893
107778486
764093
0
494428
0
0
29485241
9487534
0
5838101
-1535147
0
7657738
0
0
0
7544545
549150
0
0
...

result:

ok 99824 numbers

Test #24:

score: 20
Accepted
time: 426ms
memory: 199128kb

input:

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

output:

0
-64315
-163496
-223740
-223740
-223740
-44747751850
-223740
-223740
-44747751850
-44747675989
-304846
-1060873
-384787
-83124207796
-415624
-83124207796
-415624
-89115907284
-445584
-81452730624
-407269
-1073138
-64015213736
-64015197014
-783698
-44386769018
-40743102806
-203724
-203724
-127973
-1...

result:

ok 99424 numbers

Test #25:

score: 20
Accepted
time: 604ms
memory: 283896kb

input:

200000 199999
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 ...

output:

-247348086
1434740286
-1524312023
3809981289
606727275
5988202382
5271048050
4719901598
8499996023
16216145468
21064688094
2665101708
8277403860
4154594932
11291335137
35225541726
54762111711
5736782908
31420528368
3107673894
53293512093
50575486849
56997526602
29562546078
5151583805
30207919365
629...

result:

ok 100511 numbers

Test #26:

score: 20
Accepted
time: 996ms
memory: 315688kb

input:

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

output:

86113085
88628010
9886322444
36673546131
29712770315
19933256782
49463
14323937185
43298798461
7345167375
0
656404
243261
39013424629
38765952020
4504470725
42297162320
18841848143
53912981070
5529577816
48307919109
12128088002
54010666153
10265
11438722578
164786296
904972244
6689177880
28586348334...

result:

ok 99751 numbers

Subtask #8:

score: 20
Accepted

Dependency #2:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #6:

100%
Accepted

Dependency #7:

100%
Accepted

Test #27:

score: 20
Accepted
time: 1965ms
memory: 466344kb

input:

200000 200000
7451 2
167447 3
79959 4
193949 5
61023 6
37039 7
146491 8
98364 9
150135 10
166392 11
29518 12
23718 13
36169 14
9517 15
73336 16
48482 17
102677 18
39250 19
16931 20
176498 21
14274 22
7592 23
137421 24
162668 25
106642 26
48287 27
3133 28
26038 29
184575 30
68783 31
66137 32
155233 3...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-41949610
-32453118
0
80067
32966
0
39098
80067
23566471
0
0
0
0
80067
0
47562
0
0
51794510
0
70722
5780257
0
0
111691
0
0
0
0
0
0
0
-654011
4695332
-4666459
0
0
0
6866986
38446472
-20551288
0
0
111691
111691
111691
75841176
-8781467
-9921213
47753877
63574
0
0
0
8921...

result:

ok 133040 numbers

Test #28:

score: 20
Accepted
time: 1824ms
memory: 457700kb

input:

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

output:

0
3196760
0
45668
0
0
2427299
-2062760
0
10410344
0
5354041
184012
0
0
0
0
0
12138387
134040
0
0
45668
113370
0
0
0
-21921109
0
0
0
0
0
277281
-108237178
0
277281
0
0
277281
0
-28645166
161833
6010447
0
0
428028
428028
428028
428028
428028
0
0
428028
1611475
0
428028
1192041
428028
0
0
0
0
31399366
...

result:

ok 133279 numbers

Test #29:

score: 20
Accepted
time: 427ms
memory: 197064kb

input:

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

output:

0
9348
9348
0
0
9348
0
-1617604148
-8089
-1617604148
-8089
45147
-8089
-31629
-6325580608
-7357
-7357
-72243
-14448436423
-72243
-72243
-72243
-14448354566
-72243
-14448354566
-14448354566
-72243
-7357
-9198212109
9984
9984
9984
96368
9984
9984
1996812402
-126013
-126013
-126013
-126013
-126013
-126...

result:

ok 133664 numbers

Test #30:

score: 20
Accepted
time: 605ms
memory: 283916kb

input:

200000 200000
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 ...

output:

0
0
0
0
0
0
16966694097
187578
255807
5263110112
95819
351626
16804557732
351626
351626
2566553774
351626
16238912127
26087557170
95819
19443945985
29112263390
31263752369
153918
352223
240043
12277508096
286332
12214811892
34988952239
527939
37764193403
180425
19017192067
18164936091
527939
6066019...

result:

ok 133361 numbers

Test #31:

score: 20
Accepted
time: 1137ms
memory: 317868kb

input:

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

output:

0
0
0
0
63195
-1625332629
-2449389201
63195
0
63834
2806019700
51060
6085392327
63834
63834
143940
108702
63834
-485975625
189148
189148
189148
81085
2859242150
0
194857
1648745931
7622206012
263702
309197
5378166553
-2188493303
0
309197
240293
-1784279666
309197
109329
7554564487
0
313257757
474431...

result:

ok 133198 numbers

Test #32:

score: 20
Accepted
time: 1970ms
memory: 466484kb

input:

200000 200000
179553 2
41056 3
66398 4
37559 5
57395 6
117793 7
92737 8
120234 9
122370 10
29138 11
12908 12
110207 13
67267 14
177034 15
109705 16
198675 17
177922 18
80850 19
159377 20
99567 21
192715 22
48774 23
10949 24
101698 25
83412 26
152358 27
109287 28
124429 29
111440 30
132530 31
193687 ...

output:

0
0
78282
-2397460
0
0
0
78282
-17041143
0
0
0
65835
0
0
0
0
0
78282
69351
0
0
0
517268
69351
0
0
44832
0
78282
44832
0
0
0
-12192998
-28481652
1218
0
0
68133
56663
-13231779
56663
0
-5050914
0
78028
0
0
78028
0
0
0
0
68133
0
0
0
-54853546
42666
78028
-34856365
0
0
0
0
101246
0
97167
0
46582743
-931...

result:

ok 133207 numbers

Test #33:

score: 20
Accepted
time: 1779ms
memory: 456800kb

input:

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

output:

0
0
-5251387
0
-20204
0
0
-2629958
0
0
0
-4898517
0
89571
0
0
-741164
0
0
112583
0
0
0
0
-480166
63220
0
0
10917
0
0
0
-144136
0
-11960304
-9034928
30404
0
63220
-2554656
0
30404
-119802
63220
91226
252587
0
80309
86087
0
0
200284
2173069
0
0
0
0
43054618
0
0
0
252587
646200
68161
11174153
0
-237176...

result:

ok 133529 numbers

Test #34:

score: 20
Accepted
time: 400ms
memory: 196904kb

input:

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

output:

0
170714
0
0
280883
0
0
279738
93246
279738
43647
8729694792
43647
68823
13764869616
100344
100344
193730
100344
190918
238040
47608201882
331426
714120
714120
714120
238040
47608269676
714120
238040
714120
47608269676
299652
299652
299652
299652
299652
59930675015
393038
898956
898956
299652
393038...

result:

ok 133694 numbers

Test #35:

score: 20
Accepted
time: 583ms
memory: 281860kb

input:

200000 200000
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 ...

output:

96476
96476
178879
4838071674
5842515066
24176189527
7014110716
10659229031
618407687
23356036670
10903317080
12562350419
183038
29074228626
360804
60813088196
418443
482411
17027854222
43310450104
18885366064
572100
572100
11413699299
572100
5243070530
523074
572100
572100
572100
495157
572100
8066...

result:

ok 133216 numbers

Test #36:

score: 20
Accepted
time: 1101ms
memory: 314332kb

input:

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

output:

0
0
0
0
0
0
0
0
-87851
0
-87851
-5613376949
0
-4423702462
1702702488
-4459136047
146858
0
-2249269711
-671802418
54857
-1175550264
146858
-837292363
-6453164445
11105
-28403
-479495059
13140
13140
146858
-10118480766
-11337802238
41543
181182
0
-291
-19203
34324
1138032367
-5998320565
-28403
34324
7...

result:

ok 133025 numbers