QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#807118#7961. 一棵树dxbtAC ✓413ms106176kbC++141.2kb2024-12-09 19:03:042024-12-09 19:03:05

Judging History

This is the latest submission verdict.

  • [2024-12-09 19:03:05]
  • Judged
  • Verdict: AC
  • Time: 413ms
  • Memory: 106176kb
Show
  • [2024-12-09 19:03:04]
  • Submitted

answer

#include<bits/stdc++.h>
#define F(i,l,r) for(int i=(l),i##end=(r);i<=i##end;++i)
#define ep emplace_back
using namespace std;
typedef long long ll;
constexpr int N=5e5;
priority_queue<ll,vector<ll>,less<ll> > q[N+9];
int n,k;vector<int> E[N+9];int tag[N+9];
int gen;
int dfs1(int x,int fa)
{
	int sz=1,mx=0;
	for(auto u:E[x])
		if(u!=fa)
		{
			int t=dfs1(u,x);
			sz+=t;
			mx=max(mx,t);
		}
		if(sz>n/2&&mx<=n/2) gen=x;
	return sz;
}
void dfs(int x,int fa)
{
	q[x].push(0);
	for(auto u:E[x])
	{
		if(u==fa)continue;
		dfs(u,x);
		if(q[u].size()>q[x].size())swap(q[x],q[u]),swap(tag[x],tag[u]);
		while(!q[u].empty())q[x].push(q[u].top()+tag[u]-tag[x]),q[u].pop();
	}
	if(fa)
	{
		while(q[x].size()>(k+1)/2) q[x].pop();
		tag[x]-=2;
		if(k&1&&q[x].size()==(k+1)/2)
		{
			ll p=q[x].top();
			q[x].pop();
			q[x].push(p+2);
		}
	}
}
int main()
{
	cin.tie(0)->sync_with_stdio(false);
	cin>>n>>k;
	F(i,1,n-1)
	{
		int u,v;
		cin>>u>>v;
		E[u].ep(v);
		E[v].ep(u);
	}
	dfs1(1,0);
	dfs(gen,0);
	ll ans=1ll*(n-1)*k;
	while(q[gen].size()>k)q[gen].pop();
	F(i,1,k)
	{
		ans+=q[gen].top()+tag[gen];
		q[gen].pop();
	}
	cout<<ans<<'\n';
	return 0;
}
源文件, 语言: C++14

詳細信息

Test #1:

score: 100
Accepted
time: 390ms
memory: 84448kb

input:

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

output:

15734930984

result:

ok single line: '15734930984'

Test #2:

score: 0
Accepted
time: 192ms
memory: 83520kb

input:

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

output:

195357165512

result:

ok single line: '195357165512'

Test #3:

score: 0
Accepted
time: 150ms
memory: 79172kb

input:

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

output:

65062419628

result:

ok single line: '65062419628'

Test #4:

score: 0
Accepted
time: 135ms
memory: 76704kb

input:

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

output:

285905307

result:

ok single line: '285905307'

Test #5:

score: 0
Accepted
time: 149ms
memory: 77160kb

input:

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

output:

98388719

result:

ok single line: '98388719'

Test #6:

score: 0
Accepted
time: 162ms
memory: 82476kb

input:

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

output:

174917393258

result:

ok single line: '174917393258'

Test #7:

score: 0
Accepted
time: 145ms
memory: 76668kb

input:

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

output:

299869724

result:

ok single line: '299869724'

Test #8:

score: 0
Accepted
time: 166ms
memory: 106176kb

input:

499994 469174
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:

110061651964

result:

ok single line: '110061651964'

Test #9:

score: 0
Accepted
time: 115ms
memory: 99440kb

input:

499994 688
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
...

output:

235984

result:

ok single line: '235984'

Test #10:

score: 0
Accepted
time: 126ms
memory: 101524kb

input:

499990 141264
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:

9977617584

result:

ok single line: '9977617584'

Test #11:

score: 0
Accepted
time: 150ms
memory: 101796kb

input:

499999 210371
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:

22128058078

result:

ok single line: '22128058078'

Test #12:

score: 0
Accepted
time: 413ms
memory: 89908kb

input:

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

output:

213979261810

result:

ok single line: '213979261810'

Test #13:

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

input:

1 1

output:

0

result:

ok single line: '0'

Test #14:

score: 0
Accepted
time: 407ms
memory: 88552kb

input:

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

output:

224515847140

result:

ok single line: '224515847140'

Test #15:

score: 0
Accepted
time: 412ms
memory: 88236kb

input:

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

output:

148478316284

result:

ok single line: '148478316284'

Test #16:

score: 0
Accepted
time: 273ms
memory: 78584kb

input:

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

output:

309963582

result:

ok single line: '309963582'

Test #17:

score: 0
Accepted
time: 381ms
memory: 87980kb

input:

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

output:

132267626666

result:

ok single line: '132267626666'

Test #18:

score: 0
Accepted
time: 151ms
memory: 77024kb

input:

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

output:

89992070

result:

ok single line: '89992070'

Test #19:

score: 0
Accepted
time: 144ms
memory: 77120kb

input:

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

output:

334159450

result:

ok single line: '334159450'

Test #20:

score: 0
Accepted
time: 139ms
memory: 77044kb

input:

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

output:

312803574

result:

ok single line: '312803574'
English 繁體中文 简体中文

伺服器時間: 2025-02-08 21:04:36 | 開源專案