UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#197485#2732. 8.4t2snow_trace100685ms48720kbC++112.0kb2023-11-12 11:47:392023-11-12 12:28:04

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
vector<int>p[200005];
int pre[200005],sz[200005],ans[200005],f[200005],sum[200005];multiset<int>s[200005];
void dfs1(int now,int fa){
	sz[now] = 1;f[now] = fa;
	for(int i= 0;i<p[now].size();i++){
		if(p[now][i] == fa)continue;
		dfs1(p[now][i],now);sz[now] +=sz[p[now][i]];pre[now]+=pre[p[now][i]];
	}int sm = 0,mx = 0;
	for(int i =0;i<p[now].size();i++){
		if(p[now][i] == fa)continue;
		sm+=sz[p[now][i]]*(n-sz[p[now][i]]),mx = max(mx,sz[p[now][i]]*(n-sz[p[now][i]]));s[now].insert(sz[p[now][i]]*(n-sz[p[now][i]]));
	}pre[now]+=sm-mx;sum[now] = sm;
}void dfs2(int now){
//	cout << now << endl;
//	for(int i = 1;i<=n;i++)cout << sz[i] <<" ";cout << endl;
	for(int i =0;i<p[now].size();i++){
		if(p[now][i] == f[now])continue;
		ans[p[now][i]] = ans[now];
		int szx = sz[now],szp = sz[p[now][i]];
		int mx = 0;
		//cout << p[now][i] << endl;
		ans[p[now][i]] -=sum[p[now][i]]-(*s[p[now][i]].rbegin())+sum[now]-(*s[now].rbegin());
		sum[now]-=sz[p[now][i]]*(n-sz[p[now][i]]);s[now].erase(s[now].find(sz[p[now][i]]*(n-sz[p[now][i]])));
		sum[p[now][i]]+= sz[p[now][i]]*(n-sz[p[now][i]]);s[p[now][i]].insert(sz[p[now][i]]*(n-sz[p[now][i]]));
		sz[now] = n-sz[p[now][i]];sz[p[now][i]] = n;
		ans[p[now][i]] +=sum[p[now][i]]-(*s[p[now][i]].rbegin())+sum[now]-(*s[now].rbegin());
		//cout << p[now][i] << endl;
		dfs2(p[now][i]);
		sz[p[now][i]] = szp,sz[now] = szx;
		sum[now]+=sz[p[now][i]]*(n-sz[p[now][i]]);s[now].insert(sz[p[now][i]]*(n-sz[p[now][i]]));
		sum[p[now][i]]-= sz[p[now][i]]*(n-sz[p[now][i]]);s[p[now][i]].erase(s[p[now][i]].find(sz[p[now][i]]*(n-sz[p[now][i]])));
	//	dfs2(p[now][i]);
	}
}
signed main(){
	ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
	cin >> n;
	for(int i = 1;i<=n;i++)s[i].insert(0);
	for(int i = 1;i<n;i++){
		int a,b;cin >> a >> b;
		p[a].push_back(b),p[b].push_back(a);
	}dfs1(1,1);ans[1] = pre[1];dfs2(1);
	for(int i = 1;i<=n;i++)cout << ans[i] << '\n';
	return 0;
}

Details

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

Test #1:

score: 10
Accepted
time: 0ms
memory: 23132kb

input:

1


output:

0

result:

ok 1 number(s): "0"

Test #2:

score: 10
Accepted
time: 0ms
memory: 23160kb

input:

93
1 2
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 2...

output:

8074
8382
8232
8074
7992
7908
7822
7734
7644
7552
7982
7982
7810
7982
7984
7982
7984
7984
7982
7982
...

result:

ok 93 numbers

Test #3:

score: 10
Accepted
time: 0ms
memory: 23156kb

input:

80
1 2
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...

output:

5999
6206
6139
6070
5999
5926
5851
5774
5922
5920
5847
5920
5920
5920
5920
5920
5922
5924
5924
5920
...

result:

ok 80 numbers

Test #4:

score: 10
Accepted
time: 0ms
memory: 23272kb

input:

846
1 2
1 86
1 87
1 88
1 89
1 90
1 91
1 92
1 93
1 94
1 95
1 96
1 97
1 98
1 99
1 100
1 101
1 102
1 10...

output:

699483
782904
782307
781708
781107
780504
779899
779292
776844
776227
775608
774987
774364
773739
77...

result:

ok 846 numbers

Test #5:

score: 10
Accepted
time: 6ms
memory: 23296kb

input:

978
1 2
1 99
1 100
1 101
1 102
1 103
1 104
1 105
1 106
1 107
1 108
1 109
1 110
1 111
1 112
1 113
1 1...

output:

930868
1047985
1046629
1045948
1045265
1044580
1043893
1043204
1042513
1041820
1041125
1039028
10376...

result:

ok 978 numbers

Test #6:

score: 10
Accepted
time: 0ms
memory: 23276kb

input:

889
1 2
1 7
1 9
1 12
1 24
1 34
1 165
1 388
1 463
2 3
2 4
2 5
2 8
2 17
2 25
2 54
2 377
2 431
2 433
3 ...

output:

1630506
1683636
1660984
1645000
1681986
1676148
1611330
1626804
1624146
1586566
1609564
1619738
1598...

result:

ok 889 numbers

Test #7:

score: 10
Accepted
time: 246ms
memory: 48720kb

input:

194982
1 2
1 4
1 15
1 188
1 204
1 277
1 811
1 3825
1 13446
1 69128
1 82430
1 90085
1 112984
2 3
2 6
...

output:

155656369604
156773712623
155850308888
153750034143
151292096804
156052723034
153739534686
152708182...

result:

ok 194982 numbers

Test #8:

score: 10
Accepted
time: 107ms
memory: 38256kb

input:

105113
1 2
1 10513
1 10514
1 10515
1 10516
1 10517
1 10518
1 10519
1 10520
1 10521
1 10522
1 10523
1...

output:

10737804132
12278553554
12278343968
12278204234
12278064492
12277994618
12277505444
12277435554
1227...

result:

ok 105113 numbers

Test #9:

score: 10
Accepted
time: 159ms
memory: 48340kb

input:

174754
1 2
1 17477
1 17478
1 17479
1 17480
1 17481
1 17482
1 17483
1 17484
1 17485
1 17486
1 17487
1...

output:

29665867752
33931434312
33931318267
33931202220
33930854067
33930621955
33930505896
33930389835
3393...

result:

ok 174754 numbers

Test #10:

score: 10
Accepted
time: 167ms
memory: 47656kb

input:

171312
1 2
1 17133
1 17134
1 17135
1 17136
1 17137
1 17138
1 17139
1 17140
1 17141
1 17142
1 17143
1...

output:

28549122346
32628401242
32628287137
32628173030
32628058921
32627944810
32627830697
32627488346
3262...

result:

ok 171312 numbers