QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#762062#7767. 数据结构zhouhuanyi45 2153ms422672kbC++177.1kb2024-11-19 13:11:422024-11-19 13:11:43

Judging History

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

  • [2024-11-19 13:11:43]
  • 评测
  • 测评结果:45
  • 用时:2153ms
  • 内存:422672kb
  • [2024-11-19 13:11:42]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 200000
using namespace std;
int read()
{
	char c=0;
	int sum=0,f=1;
	while (c!='-'&&(c<'0'||c>'9')) c=getchar();
	if (c=='-') c=getchar(),f=-1;
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum*f;
}
struct reads
{
	int l,r;
};
reads operator + (reads a,reads b)
{
	return (reads){min(a.l,b.l),max(a.r,b.r)};
}
struct lines
{
	int x,y,data;
	bool operator < (const lines &t)const
	{
		return data<t.data;	
	}
};
lines dque[N+1];
int n,m,tops,dfn[N+1],leng,depth[N+1],rev[N+1],rev2[N+1],sz[N+1],top[N+1],fa[N+1],hs[N+1],num[N+1],length;
__int128 ans;
bool used[N+1];
vector<int>E[N+1];
vector<int>ES[N+1];
vector<int>p[N+1][4];
vector<reads>dp[N+1][4];
vector<reads>DP[N+1][4];
vector<reads>DP2[N+1];
vector<reads>operator + (vector<reads>a,vector<reads>b)
{
	if (a.empty()) return b;
	if (b.empty()) return a;
	int ps=0,ps2=0;
	reads d=(reads){0,-1};
	vector<reads>sp;
	while (ps<a.size()||ps2<b.size())
	{
		if (ps<a.size()&&(ps2==b.size()||a[ps].l<b[ps2].l))
		{
			if (d.r+1>=a[ps].l) d=d+a[ps];
			else
			{
				if (d.l<=d.r) sp.push_back(d);
				d=a[ps];
			}
			ps++;
		}
		else
		{
			if (d.r+1>=b[ps2].l) d=d+b[ps2];
			else
			{
				if (d.l<=d.r) sp.push_back(d);
				d=b[ps2];
			}
			ps2++;
		}
	}
	sp.push_back(d);
	return sp;
}
vector<reads>operator * (vector<reads>a,vector<reads>b)
{
	if (a.empty()) return b;
	if (b.empty()) return a;
	int ps=0,ps2=0;
	reads d=(reads){0,-1};
	vector<reads>sp;
	while (ps<a.size()||ps2<b.size())
	{
		if (ps<a.size()&&(ps2==b.size()||a[ps].l<b[ps2].l))
		{
			if (d.r+1>=a[ps].l) d=d+a[ps];
			else
			{
				if (d.l<=d.r) sp.push_back(d);
				d=a[ps];
			}
			ps++;
		}
		else
		{
			if (d.r+1>=b[ps2].l) d=d+b[ps2];
			else
			{
				if (d.l<=d.r) sp.push_back(d);
				d=b[ps2];
			}
			ps2++;
		}
	}
	sp.push_back(d);
	if (sp.size()>=40) sp.clear(),sp.shrink_to_fit();
	return sp;
}
void add(int x,int y)
{
	E[x].push_back(y),E[y].push_back(x);
	return;
}
void dfs(int x)
{
	used[x]=sz[x]=1;
	for (int i=0;i<E[x].size();++i)
		if (!used[E[x][i]])
		{
			fa[E[x][i]]=x,depth[E[x][i]]=depth[x]+1,ES[x].push_back(E[x][i]),dfs(E[x][i]),sz[x]+=sz[E[x][i]];
			if (sz[E[x][i]]>sz[hs[x]]) hs[x]=E[x][i];
		}
	return;
}
void dfs2(int x)
{
	dfn[x]=++leng,rev[dfn[x]]=x;
	if (ES[x].empty()) dque[++tops]=(lines){top[x],x,depth[top[x]]};
	if (hs[x]) top[hs[x]]=top[x],dfs2(hs[x]);
	for (int i=0;i<ES[x].size();++i)
		if (ES[x][i]!=hs[x])
			top[ES[x][i]]=ES[x][i],dfs2(ES[x][i]);
	return;
}
void dfs3(int x)
{
	for (int i=0;i<ES[x].size();++i)
	{
		if (ES[x][i]==hs[x])
		{
			for (int j=0;j<=3;++j) DP[ES[x][i]][j]=DP[ES[x][i]][j]+DP[x][j];
		}
		dfs3(ES[x][i]),DP2[x]=DP2[x]+DP2[ES[x][i]];
	}
	return;
}
struct seg
{
	struct node
	{
		int l,r;
		vector<reads>data;
	};
	node tree[(N<<2)+1];
	void push_up(int k)
	{
		tree[k].data=tree[k<<1].data*tree[k<<1|1].data;
		return;
	}
	void build(int k,int l,int r,int d)
	{
		tree[k].l=l,tree[k].r=r;
		if (l==r)
		{
			tree[k].data=dp[rev[l]][d];
			return;
		}
		int mid=(l+r)>>1;
		build(k<<1,l,mid,d),build(k<<1|1,mid+1,r,d),push_up(k);
		return;
	}
	vector<reads>query(int k,int l,int r)
	{
		if (tree[k].l==l&&tree[k].r==r) return tree[k].data;
		int mid=(tree[k].l+tree[k].r)>>1;
		if (r<=mid) return query(k<<1,l,r);
		else if (l>=mid+1) return query(k<<1|1,l,r);
		else return query(k<<1,l,mid)*query(k<<1|1,mid+1,r);
	}
};
seg T[4];
struct seg2
{
	struct node
	{
		int l,r;
		long long lazy;
		__int128 data;
	};
	node tree[(N<<2)+1];
	void push_up(int k)
	{
		tree[k].data=tree[k<<1].data+tree[k<<1|1].data;
		return;
	}
	void push_tag(int k,long long d)
	{
		tree[k].lazy+=d,tree[k].data+=(__int128)(d)*(tree[k].r-tree[k].l+1);
		return;
	}
	void spread(int k)
	{
		if (tree[k].lazy!=0) push_tag(k<<1,tree[k].lazy),push_tag(k<<1|1,tree[k].lazy),tree[k].lazy=0;
		return;
	}
	void build(int k,int l,int r)
	{
		tree[k].l=l,tree[k].r=r;
		if (l==r) return;
		int mid=(l+r)>>1;
		build(k<<1,l,mid),build(k<<1|1,mid+1,r),push_up(k);
		return;
	}
	void add(int k,int l,int r,int d)
	{
		if (tree[k].l==l&&tree[k].r==r)
		{
			push_tag(k,d);
			return;
		}
		spread(k);
		int mid=(tree[k].l+tree[k].r)>>1;
		if (r<=mid) add(k<<1,l,r,d);
		else if (l>=mid+1) add(k<<1|1,l,r,d);
		else add(k<<1,l,mid,d),add(k<<1|1,mid+1,r,d);
		push_up(k);
		return;
	}
	__int128 query(int k,int l,int r)
	{
		if (tree[k].l==l&&tree[k].r==r) return tree[k].data;
		spread(k);
		int mid=(tree[k].l+tree[k].r)>>1;
		if (r<=mid) return query(k<<1,l,r);
		else if (l>=mid+1) return query(k<<1|1,l,r);
		else return query(k<<1,l,mid)+query(k<<1|1,mid+1,r);
	}
};
seg2 T2;
vector<reads>get_path(int x,int y,int k)
{
	vector<reads>sp;
	while (top[x]!=top[y])
	{
		if (depth[top[x]]<depth[top[y]]) swap(x,y);
		sp=sp+DP[x][k],x=fa[top[x]];
	}
	if (depth[x]>depth[y]) swap(x,y);
	sp=sp+T[k].query(1,dfn[x],dfn[y]);
	return sp;
}
void write(__int128 d)
{
	if (!d) return;
	write(d/10),printf("%d",(int)(d%10));
	return;
}
void output(__int128 d)
{
	if (d>0) write(d),puts("");
	else if (d==0) puts("0");
	else printf("-"),write(-d),puts("");
	return;
}
int main()
{
	int opt,x,y,d,k;
	vector<reads>sp;
	n=read(),m=read();
	for (int i=1;i<=n-1;++i) x=read(),y=read(),add(x,y);
	depth[1]=1,dfs(1);
	for (int i=1;i<=n;++i)
	{
		x=i;
		for (int j=0;j<=3;++j)
		{
			if (x) p[x][j].push_back(i);
			x=fa[x];
		}
	}
	top[1]=1,dfs2(1),sort(dque+1,dque+tops+1);
	for (int i=1;i<=tops;++i)
	{
		x=dque[i].x;
		while (x)
		{
			if (!num[x]) num[x]=++length;
			x=hs[x];
		}
		for (int j=0;j<=2;++j)
		{
			x=dque[i].x;
			while (x)
			{
				for (int k=0;k<E[x].size();++k)
					if (E[x][k]!=hs[x])
					{
						for (int t=0;t<p[E[x][k]][j].size();++t)
							if (!num[p[E[x][k]][j][t]])
								num[p[E[x][k]][j][t]]=++length;
					}
				x=hs[x];
			}
		}
	}
	for (int i=1;i<=n;++i) dp[i][0]={(reads){num[i],num[i]}},rev2[num[i]]=i;
	for (int i=1;i<=3;++i)
		for (int j=1;j<=n;++j)
		{
			dp[j][i]=dp[j][i-1];
			for (int t=0;t<E[j].size();++t) dp[j][i]=dp[j][i]+dp[E[j][t]][i-1];
		}
	for (int i=1;i<=n;++i)
	{
		for (int j=0;j<=3;++j) DP[i][j]=dp[i][j];
		DP2[i]=dp[i][0];
	}
	dfs3(1);
	for (int i=0;i<=3;++i) T[i].build(1,1,n,i);
	T2.build(1,1,n);
	for (int qt=1;qt<=m;++qt)
	{
		opt=read();
		if (opt==1)
		{
			x=read(),y=read(),k=read(),d=read(),sp=get_path(x,y,k);
			for (int i=0;i<sp.size();++i) T2.add(1,sp[i].l,sp[i].r,d);
		}
		else if (opt==2)
		{
			x=read(),d=read(),sp=DP2[x];
			for (int i=0;i<sp.size();++i) T2.add(1,sp[i].l,sp[i].r,d);
		}
		else if (opt==3)
		{
			x=read(),y=read(),k=read(),sp=get_path(x,y,k),ans=0;
			for (int i=0;i<sp.size();++i) ans+=T2.query(1,sp[i].l,sp[i].r);
			printf("%llu\n",(unsigned long long)(ans));
		}
		else
		{
			x=read(),sp=DP2[x],ans=0;
			for (int i=0;i<sp.size();++i) ans+=T2.query(1,sp[i].l,sp[i].r);
			printf("%llu\n",(unsigned long long)(ans));
		}
	}
	return 0;
}

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 55ms
memory: 181128kb

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: 52ms
memory: 181452kb

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: 1712ms
memory: 415224kb

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: 2153ms
memory: 412960kb

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: 623ms
memory: 388216kb

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: 622ms
memory: 385824kb

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: 1310ms
memory: 416712kb

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: 783ms
memory: 388036kb

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: 1352ms
memory: 411744kb

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: 1409ms
memory: 416248kb

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: 1370ms
memory: 422672kb

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: 0
Memory Limit Exceeded

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #12:

score: 15
Accepted
time: 1216ms
memory: 415652kb

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: 0
Memory Limit Exceeded

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:


Subtask #7:

score: 0
Time Limit Exceeded

Dependency #2:

100%
Accepted

Dependency #4:

100%
Accepted

Test #17:

score: 15
Accepted
time: 1941ms
memory: 416720kb

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: 0
Time Limit Exceeded

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:

1255
2433795
1964764
29610
23717
31723
3955911
23645
26156
24271
0
5061986
44062
10493949
985908
8761
10779313
10728779
9340774
67665
15346404
65472
14456534
63561
61791
68174
1589016
68134
71263
1927247
1819693
83323
85878
1305563
24227309
101761
92443
17871367
25711555
96440
14314220
109965
127220...

result:


Subtask #8:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

0%