UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#213295#3849. 旅行日记shiruiheng20421ms16324kbC++111.7kb2024-11-10 12:46:202024-11-10 13:08:25

answer

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
//using LL = __int128
#define pi pair<ll, ll>
#define fi first
#define se second
#define N 111111
//#define fi(x) (x->first)
//#define se(x) (x->second)
vector<ll> g[N];
ll n, s, u, v, fa[N], vis[N], sz[N], val[N], sum[N], cnt, ans;
void add(int u, int v){
	g[u].push_back(v);
}
bool cmp(int u, int v){
	return sz[u] * val[v] > sz[v] * val[u];
}
ll calc(int u, int v){
	return sz[v] * val[u] - sz[u] * val[v];
}
void pre(int u, int f){
	fa[u] = f;
	sz[u] = 1;
	val[u] = u;
	for(auto v : g[u]){
		if(v == f)
			continue;
		pre(v, u);
		sz[u] += sz[v];
		val[u] += val[v];
	}
}
void dfs(int u, int f){
	if(!vis[u]){
		ans += u * (++cnt), vis[u] = true;
	}
	for(auto v : g[u]){
		if(v == f)
			continue;
		dfs(v, u);
	}
}
int main(){
	mt19937_64 gen(time(0));
	scanf("%lld%lld", &n, &s);
	for(int i = 1 ; i < n ; i++){
		scanf("%lld%lld", &u, &v);
		add(u, v);
		add(v, u);
	}
	pre(s, s);
	if(sz[1] >= n - 1){
		sort(g[1].begin(), g[1].end());
	}
	else if(n >= 18){
		for(int i = 1 ; i <= n ; i++){
			for(int j = 0 ; j < g[i].size() ; j++){
				for(int k = 1 ; k < g[i].size() ; k++)
					if(calc(g[i][k], g[i][k - 1]) <= 0)
						swap(g[i][k], g[i][k - 1]);
			}
		}
	}
	else{
		ll ans1 = 0;
		for(int k = 1 ; k <= __lg(20 * n) ; k++){
			ans = cnt = 0;
			for(int i = 1 ; i <= n ; i++){
				shuffle(g[i].begin(), g[i].end(), gen);
				sort(g[i].begin(), g[i].end(), cmp);
			}
			dfs(s, s);
			ans1 = max(ans1, ans);
		}
		printf("%lld", ans1);
		return 0;
	}
	dfs(s, s);
	printf("%lld", ans);
	return 0;
}
/*
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);

*/

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3872kb

input:

10 6
5 8
3 8
9 8
10 3
6 8
7 10
1 7
2 5
4 10

output:

303

result:

wrong answer 1st numbers differ - expected: '304', found: '303'

Test #2:

score: 0
Wrong Answer
time: 0ms
memory: 3864kb

input:

10 7
1 5
10 1
6 5
7 5
4 6
8 6
2 6
3 6
9 1

output:

327

result:

wrong answer 1st numbers differ - expected: '345', found: '327'

Test #3:

score: 0
Wrong Answer
time: 2ms
memory: 3868kb

input:

10 9
4 9
8 9
1 8
6 4
5 1
2 4
10 8
3 6
7 3

output:

313

result:

wrong answer 1st numbers differ - expected: '320', found: '313'

Test #4:

score: 0
Wrong Answer
time: 3ms
memory: 3868kb

input:

10 7
6 1
2 1
8 2
4 6
9 2
10 2
7 6
3 10
5 4

output:

324

result:

wrong answer 1st numbers differ - expected: '336', found: '324'

Test #5:

score: 0
Wrong Answer
time: 0ms
memory: 3864kb

input:

18 10
11 16
15 11
5 11
7 16
17 15
13 16
8 13
9 5
12 13
14 8
4 5
18 4
2 4
10 16
3 16
1 10
6 9

output:

1822

result:

wrong answer 1st numbers differ - expected: '1911', found: '1822'

Test #6:

score: 0
Wrong Answer
time: 0ms
memory: 3872kb

input:

18 15
8 16
13 16
7 13
2 13
9 8
5 9
3 13
15 5
1 13
4 3
18 9
14 4
17 2
12 13
10 5
11 1
6 18

output:

1656

result:

wrong answer 1st numbers differ - expected: '1750', found: '1656'

Test #7:

score: 0
Wrong Answer
time: 0ms
memory: 3864kb

input:

18 1
17 9
12 17
3 12
8 9
14 17
15 3
18 15
4 3
11 9
16 3
6 15
2 11
5 8
10 5
1 12
7 5
13 1

output:

1724

result:

wrong answer 1st numbers differ - expected: '1895', found: '1724'

Test #8:

score: 0
Wrong Answer
time: 0ms
memory: 3872kb

input:

18 15
10 11
9 10
16 9
17 10
6 10
12 16
13 11
15 10
8 13
7 8
5 16
4 13
1 15
18 16
14 7
2 18
3 18

output:

1704

result:

wrong answer 1st numbers differ - expected: '1728', found: '1704'

Test #9:

score: 5
Accepted
time: 45ms
memory: 10852kb

input:

100000 16441
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
...

output:

333338198204980

result:

ok 1 number(s): "333338198204980"

Test #10:

score: 5
Accepted
time: 22ms
memory: 10856kb

input:

100000 99177
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
...

output:

333333415360924

result:

ok 1 number(s): "333333415360924"

Test #11:

score: 5
Accepted
time: 16ms
memory: 10856kb

input:

100000 59601
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
...

output:

333336557240200

result:

ok 1 number(s): "333336557240200"

Test #12:

score: 5
Accepted
time: 12ms
memory: 10856kb

input:

100000 30655
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
...

output:

333337863500815

result:

ok 1 number(s): "333337863500815"

Test #13:

score: 0
Wrong Answer
time: 42ms
memory: 16032kb

input:

100000 53503
15420 17742
17742 64232
64232 17523
17523 33388
33388 73908
73908 15412
15412 67920
679...

output:

250355925087320

result:

wrong answer 1st numbers differ - expected: '250413064505673', found: '250355925087320'

Test #14:

score: 0
Wrong Answer
time: 50ms
memory: 15276kb

input:

100000 5700
95638 43692
43692 52040
52040 29909
29909 66571
66571 20077
20077 28853
28853 20470
2047...

output:

250311236792275

result:

wrong answer 1st numbers differ - expected: '250814390051272', found: '250311236792275'

Test #15:

score: 0
Wrong Answer
time: 36ms
memory: 16324kb

input:

100000 73165
7735 42311
42311 26035
26035 44914
44914 71359
71359 9414
9414 21996
21996 19789
19789 ...

output:

249920916430743

result:

wrong answer 1st numbers differ - expected: '249949750624627', found: '249920916430743'

Test #16:

score: 0
Wrong Answer
time: 43ms
memory: 13528kb

input:

100000 81023
86193 9869
9869 79475
79475 88553
88553 54043
54043 91736
91736 23883
23883 68360
68360...

output:

250257297095145

result:

wrong answer 1st numbers differ - expected: '250402679195507', found: '250257297095145'

Test #17:

score: 0
Wrong Answer
time: 38ms
memory: 10636kb

input:

100000 53752
20439 68430
24723 68430
12283 20439
7861 12283
73785 68430
44056 24723
22482 7861
44454...

output:

252077000601581

result:

wrong answer 1st numbers differ - expected: '296233806565812', found: '252077000601581'

Test #18:

score: 0
Wrong Answer
time: 38ms
memory: 10676kb

input:

100000 81174
36555 78900
68651 36555
12967 78900
43832 36555
12851 36555
63272 43832
23048 12967
355...

output:

253164911305232

result:

wrong answer 1st numbers differ - expected: '296033950451487', found: '253164911305232'

Test #19:

score: 0
Wrong Answer
time: 36ms
memory: 10648kb

input:

100000 2143
44484 44643
28626 44484
80384 44643
33549 44484
89306 44643
57164 44484
73721 44643
4818...

output:

252335286139049

result:

wrong answer 1st numbers differ - expected: '296156367383787', found: '252335286139049'

Test #20:

score: 0
Wrong Answer
time: 38ms
memory: 10656kb

input:

100000 82182
62671 86050
89147 86050
37496 86050
31816 89147
83680 62671
19020 83680
42399 86050
751...

output:

252160116187475

result:

wrong answer 1st numbers differ - expected: '296278552690388', found: '252160116187475'