QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#762063#7767. 数据结构Nesraychan100 ✓2189ms333348kbC++145.8kb2024-11-19 13:12:062024-11-19 13:12:16

Judging History

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

  • [2024-11-19 13:12:16]
  • 评测
  • 测评结果:100
  • 用时:2189ms
  • 内存:333348kb
  • [2024-11-19 13:12:06]
  • 提交

answer

#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 200200
#define u64 unsigned 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];
u64 sum[N<<2],tag[N<<2];

IL void pushup(reg int o){sum[o]=sum[ls]+sum[rs];}
IL void apply(reg int o,reg u64 k){sum[o]+=k*(r[o]-l[o]+1),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);
}

u64 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);
}

#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 u64 res=0;
            for(auto &[l,r]:P)
                res+=Segment::query_sum(1,l,r);
            printf("%llu\n",res);
        }else
        {
            auto P=sub[x];
            reg u64 res=0;
            for(auto &[l,r]:P)
                res+=Segment::query_sum(1,l,r);
            printf("%llu\n",res);            
        }
    }
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 41ms
memory: 100352kb

input:

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

output:

37227703492
2136305359188
2794367845468
1309925069860
1698169768858
2678958746332
6690595071246
2087826052960
5786332239171
2186592622
4014965079076
1674542130
6524658548
7094033144666
10065416610040
11589693473717
492570862
3356228199498
2834694279
4198036633070
4395772262
4221137767
9630829210
992...

result:

ok 2559 numbers

Test #2:

score: 10
Accepted
time: 53ms
memory: 102540kb

input:

5000 5000
54 2
1945 3
4131 4
1207 5
3558 6
3582 7
1648 8
3498 9
1761 10
360 11
3617 12
4359 13
158 14
2314 15
529 16
4619 17
1070 18
1504 19
2675 20
2981 21
2142 22
1349 23
1640 24
1374 25
4059 26
2511 27
2708 28
2939 29
3017 30
3320 31
4602 32
4779 33
2697 34
3906 35
1121 36
197 37
1551 38
1119 39
...

output:

0
198262395
0
0
1595057854
0
0
39277179818
13451201574
21469030838
0
0
23554220364
19140694248
212211615641
0
0
0
0
0
86500798
60136122614
47351162248
0
0
306346383502
230306838988
0
170207438
471673864986
387605196674
0
0
0
688392707
115968801311
199501119668
168720065378
634329317954
0
0
155717506...

result:

ok 2456 numbers

Subtask #2:

score: 10
Accepted

Test #3:

score: 10
Accepted
time: 1822ms
memory: 312656kb

input:

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

output:

0
0
0
0
0
0
0
0
7615073807
4176911055
0
4745654848
6222845818
0
0
9739142819
0
1424960716
5224818790
9459319003
13717923473
8673060864
0
11610197664
0
0
9587792729
0
0
0
2747489046
12425650803
0
0
11191496476
0
37597503993
0
0
15164651949
14868775382
15559673116
0
16391028892
0
15726757336
0
2421390...

result:

ok 100169 numbers

Test #4:

score: 10
Accepted
time: 2147ms
memory: 327580kb

input:

200000 200000
121679 2
13340 3
45206 4
112138 5
47397 6
88216 7
173469 8
109861 9
58662 10
130056 11
61155 12
4313 13
196310 14
46189 15
32349 16
143798 17
103215 18
159921 19
27365 20
14332 21
49504 22
64451 23
106931 24
59878 25
177587 26
100555 27
86848 28
793 29
79845 30
150813 31
42854 32
11551...

output:

77900221111
0
0
476439705914
0
216029652830
0
0
631267909751
508097390689
0
29277716182
695169620128
0
809294022024
0
0
829507748883
260130797154
0
1005527232590
109198360548
821333235719
0
0
1265757368752
738460021055
296232170804
845184728833
0
434366813420
0
1922343637889
0
0
0
229703081048
0
441...

result:

ok 100073 numbers

Subtask #3:

score: 5
Accepted

Test #5:

score: 5
Accepted
time: 622ms
memory: 273204kb

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
134315201201061
38210069287857
75889674481730
25202765567748
179527420359031
75824479907233
156951577189979
246509811214535
251383387317167
181645886595511
285463150681348
213797241401335
244909583142805
53376921005282
451665818220
379334117147250
720759810155057
768646965102274
224741692238593
18...

result:

ok 100065 numbers

Test #6:

score: 5
Accepted
time: 623ms
memory: 270960kb

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
1950387013442
2906443199266
2144858813468
3137341049831
1081425884175
20924388962208
73530126133368
136609133052209
125022026678010
22502893517249
99022896674514
84010333777754
13909990392191
43442491331837
190816082733002
92810414504491
244006706308139
42843404030538
126151201042579
7249812065288...

result:

ok 99740 numbers

Subtask #4:

score: 10
Accepted

Test #7:

score: 10
Accepted
time: 1410ms
memory: 316868kb

input:

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

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 99786 numbers

Test #8:

score: 10
Accepted
time: 928ms
memory: 256968kb

input:

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

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 100404 numbers

Test #9:

score: 10
Accepted
time: 1388ms
memory: 312956kb

input:

200000 200000
166945 2
60190 3
101888 4
154621 5
188595 6
175999 7
140051 8
54071 9
167394 10
54228 11
48270 12
14564 13
25727 14
138072 15
77670 16
77795 17
155644 18
171648 19
94412 20
65323 21
130225 22
6359 23
17410 24
8580 25
142556 26
152863 27
166869 28
115234 29
87099 30
160349 31
98200 32
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 99768 numbers

Subtask #5:

score: 10
Accepted

Dependency #4:

100%
Accepted

Test #10:

score: 10
Accepted
time: 1396ms
memory: 316412kb

input:

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

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 100258 numbers

Test #11:

score: 10
Accepted
time: 1421ms
memory: 333348kb

input:

200000 200000
184821 2
53793 3
183415 4
113765 5
178864 6
46342 7
933 8
197825 9
177971 10
143394 11
99313 12
188890 13
25495 14
60986 15
162307 16
135027 17
145920 18
109359 19
5215 20
75134 21
53020 22
160666 23
30142 24
23800 25
38903 26
121838 27
164296 28
86957 29
89705 30
108331 31
147730 32
2...

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 100336 numbers

Subtask #6:

score: 15
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #12:

score: 15
Accepted
time: 1323ms
memory: 315848kb

input:

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

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
540038770
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100044 numbers

Test #13:

score: 15
Accepted
time: 1243ms
memory: 291068kb

input:

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

output:

0
0
0
0
0
0
510
0
0
0
0
0
0
0
0
405
0
0
0
12322
0
1670
283520
0
0
0
0
0
407680
177845
0
405
0
0
0
0
1464
490
61
0
0
465860
0
16472
0
1534
265620
422870
767
0
0
0
788
280990
322
0
0
198
893
79486
0
767
0
0
0
0
0
0
40
1300
114170
14950
280978
0
0
58950
296946
436080
1512
9726
0
0
226707
325962
312984
...

result:

ok 100096 numbers

Test #14:

score: 15
Accepted
time: 1259ms
memory: 271440kb

input:

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

output:

0
0
0
0
304142
0
289115
0
224
0
576
637
154
0
0
0
0
364608
0
910496
333282
758
158646
0
1291
242188
365040
0
1333572
0
249
593761
180642
0
850
1186
0
89320
316618
704925
0
0
2475
148508
242
67518
979
0
67224
1692359
920722
3014
0
518286
0
1311330
1369518
1008436
3095052
511760
1650509
298410
1803117...

result:

ok 100062 numbers

Test #15:

score: 15
Accepted
time: 890ms
memory: 266884kb

input:

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

output:

0
0
0
0
21346853945576
48396643270631
4321029030
37003305606483
17683419927060
561778302
94539925025025
561778302
19563617093670
0
17946414540
32901956622
13400634896
1907726287
290652131875362
498785221322560
566362662702578
553392549765534
3570739868
1016393566
16079113938
119565043564896
46196526...

result:

ok 100401 numbers

Test #16:

score: 15
Accepted
time: 1381ms
memory: 319864kb

input:

200000 200000
170804 2
114218 3
118786 4
81407 5
92607 6
121128 7
39792 8
17516 9
151784 10
45071 11
109409 12
10487 13
65474 14
193833 15
28336 16
144805 17
198454 18
107320 19
181481 20
138015 21
10446 22
181869 23
174873 24
194511 25
46182 26
42247 27
111765 28
80980 29
64828 30
33044 31
133963 3...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
536682891
0
0
0
0
0
0
0
0
0
894471485
0
0
0
0
0
0
0
0
0
0
0
1073365782
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
178894297
0
0
0
0
0
0
0
0
124910174
0
69868842
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1967837267
0
0
0
42599187462
0
536682891
0
0
0
0
0
687005957
0
0
0
562095783
0
0...

result:

ok 100179 numbers

Subtask #7:

score: 15
Accepted

Dependency #2:

100%
Accepted

Dependency #4:

100%
Accepted

Test #17:

score: 15
Accepted
time: 1821ms
memory: 315580kb

input:

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

output:

0
12712803164
0
0
8193968417
14426787309
12950092190
0
32958618613
26764906955
8493139167
0
42785505564
55243799113
0
0
0
0
0
16857343623
27991363871
14151995536
55690427136
85838206842
0
26020925273
22490232861
0
0
1662166464
24948089565
0
26561191640
202942896717
0
91771091757
152033022013
2500525...

result:

ok 100098 numbers

Test #18:

score: 15
Accepted
time: 1720ms
memory: 268768kb

input:

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

output:

1506
2433795
1964764
29809
23904
32308
3956297
23683
26194
24496
0
5108618
44498
10494148
1493614
8948
11034059
10983525
9340774
68288
15623342
65908
14673691
63760
62016
68610
3785842
68409
71500
4760847
1843709
83560
86276
3800228
24415019
102280
92867
17894104
25995202
96677
14391781
110124
12872...

result:

ok 99928 numbers

Test #19:

score: 15
Accepted
time: 1933ms
memory: 298596kb

input:

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

output:

0
6432
5572
2146
5686
15024
5924
10437
10836
16481
12732
37909
15933
53994
38493
121364
89269
36850
69524
53517
239542
137860
93122
118688
151902
9279
120973
73158
28901
122575
43850
21781
119189
28818
71155
127221
157054
65948
40570
183418
150579
145757
147361
89223
4664
78041
329787
100673
50134
6...

result:

ok 100068 numbers

Subtask #8:

score: 25
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Dependency #7:

100%
Accepted

Test #20:

score: 25
Accepted
time: 2067ms
memory: 313684kb

input:

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

output:

0
0
0
0
0
465548908352
0
0
1049072790058
0
0
0
3498253875794
2462272083501
0
0
0
6241645911240
0
494213688398
2347903181100
0
3728768281280
0
0
3432108986320
0
8469184085224
0
8245898092098
8330457266913
5826089812394
364325757
0
0
4349342792270
0
12318077513275
11118693711818
12376615187747
0
12897...

result:

ok 100329 numbers

Test #21:

score: 25
Accepted
time: 1144ms
memory: 259036kb

input:

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

output:

0
0
50569487
2600333591027
50569487
1186208456559
96537150683
291583662042
280086809868243
7561410184
182540503517537
3870048686
4825881401
568246059173105
508080241347192
638856244490679
7811085998489
398136386558692
259502453457033
596111245902764
135800450617255
496697642799696
148330538161166
62...

result:

ok 99764 numbers

Test #22:

score: 25
Accepted
time: 2056ms
memory: 322604kb

input:

200000 200000
99996 2
141376 3
146563 4
140743 5
137889 6
197771 7
6239 8
173333 9
147385 10
128295 11
87732 12
17498 13
966 14
58215 15
60811 16
196395 17
94285 18
143376 19
191265 20
18708 21
88524 22
83638 23
101810 24
133133 25
130094 26
147872 27
116578 28
153022 29
115586 30
18109 31
124747 32...

output:

0
1527305572085
620328030446
1252349895193
0
274142198558
723725574040
0
0
6748890038813
2520882634927
3368554730649
4584117267462
0
0
0
0
7844925682310
0
0
12178888018305
11389166537907
0
3557014247234
9922133339986
6339953599024
197496739660
0
2983329095305
206600063302
0
8481939789945
0
765606005...

result:

ok 100107 numbers

Test #23:

score: 25
Accepted
time: 1592ms
memory: 290472kb

input:

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

output:

423234
1110315
35538
0
3527944
4277944
3618216
1511552
9308952
0
12904322
0
22098641
663
622
28191749
26780936
9092662
0
36027851
0
1606
472358
1371
310
0
0
392
1501509
21987918
750
24841528
0
45565407
37148358
758
925
741
22914923
333
0
74918832
66975866
542
0
70139339
0
333
310
68455009
63979020
0...

result:

ok 99866 numbers

Test #24:

score: 25
Accepted
time: 1577ms
memory: 280724kb

input:

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

output:

0
0
0
0
2846778
470613
3342714
0
0
189
248
838
12429934
0
14013010
9028904
778
35
12146114
33379996
0
15999772
28982761
3771
1196
0
26539634
1366
56135190
1531
0
176
6547283
0
64019039
1883
2605
778
0
39362976
0
101259306
97083211
468
99564118
40791370
365
102820163
101082181
23
42949812
96099569
98...

result:

ok 100259 numbers

Test #25:

score: 25
Accepted
time: 1537ms
memory: 289372kb

input:

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

output:

0
0
1625022
0
0
0
0
6998162
1787351
0
3906102
4953087
0
4032292
0
0
1418
0
7039728
747
21958806
21557601
1138
17182376
7669849
26064810
0
17834813
0
5910523
0
32032298
26048645
11711702
3935933
0
36155896
51214723
59781840
60644963
65108813
21861955
5246285
800
0
9453207
26622210
45582424
292
430472...

result:

ok 100024 numbers

Test #26:

score: 25
Accepted
time: 1563ms
memory: 295460kb

input:

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

output:

0
0
0
0
0
0
0
79568
0
118118
0
0
222672
120434
108951
188357
108951
0
0
0
0
254819
0
0
0
292014
0
0
0
0
364782
31464
0
0
0
0
357975
0
0
183227
0
499201
240304
0
0
223898
24931
0
469642
0
0
468822
0
0
0
0
0
346464
23464
0
0
844602
0
0
0
0
1303492
0
0
1056750
1539022
0
0
0
837735
1545534
0
1130865
110...

result:

ok 100111 numbers

Test #27:

score: 25
Accepted
time: 2189ms
memory: 282856kb

input:

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

output:

0
19862670
17258551
455435
16488539
9130379
7314072
30575340
19690141
19313936
21669613
23012451
12837945
3723195
26457564
18702581
39548020
30336071
16441097
20939995
48290384
29762374
48067566
47812904
53042833
66100909
62174100
55375354
39831643
34875945
35403493
87775179
65358326
10922360
563282...

result:

ok 100383 numbers

Test #28:

score: 25
Accepted
time: 1930ms
memory: 278300kb

input:

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

output:

0
0
0
10733666
5512532
19003243
4619784
28471100
13929668
3288853
792985
37517085
25981724
17849894
29127734
4655989
39093189
16846305
18203668
25201100
30974270
20533921
25409377
21009591
61495726
45128919
54846665
4199447
27051769
67540627
26459973
95737163
58749670
70036821
64124214
66257942
4011...

result:

ok 100285 numbers