UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#197484#2732. 8.4t2tkswls100220ms16856kbC++111.6kb2023-11-12 11:47:382023-11-12 12:28:00

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, head[200005], to[400005], nxt[400005], ccnt, son[200005], d[200005], siz[200005], f[200005], sson[200005];
inline void add(int p, int q) {
	nxt[++ccnt] = head[p];
	to[ccnt] = q;
	head[p] = ccnt;
}
inline void dfs(int p, int q) {
	siz[p] = 1;
	for (int i = head[p]; i; i = nxt[i]) {
		if (to[i] == q) continue;
		dfs(to[i], p);
		siz[p] += siz[to[i]];
		if (siz[to[i]] > siz[son[p]]) {
			sson[p] = son[p];
			son[p] = to[i];
		} else if (siz[to[i]] > siz[sson[p]]) {
			sson[p] = to[i];
		}
	}
	for (int i = head[p]; i; i = nxt[i]) {
		if (to[i] == q) continue;
		d[p] += d[to[i]];
		if (son[p] != to[i]) {
			d[p] += siz[to[i]] * (n - siz[to[i]]);
		}
	}
}
inline void ddfs(int p, int q) {
	if (p == 1) {
		f[p] = d[p];
	} else {
		f[p] = d[p] + siz[son[p]] * (n - siz[son[p]]);
		if (son[q] == p && siz[p] >= n - siz[q]) {
			f[p] += f[q] - d[p] + siz[p] * (n - siz[p]);
			if (siz[sson[q]] >= n - siz[q]) {
				f[p] -= siz[sson[q]] * (n - siz[sson[q]]);
			} else {
				f[p] -= (n - siz[q]) * siz[q];
			}
		} else {
			f[p] += f[q] - d[p];
		}
		if (siz[son[p]] >= n - siz[p]) {
			f[p] -= siz[son[p]] * (n - siz[son[p]]);
		} else {
			f[p] -= (n - siz[p]) * siz[p];
		}
	}
	for (int i = head[p]; i; i = nxt[i]) {
		if (to[i] != q) ddfs(to[i], p);
	}
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	int p, q;
	for (int i = 1; i < n; i++) {
		cin >> p >> q;
		add(p, q);
		add(q, p);
	}
	dfs(1, 0);
	ddfs(1, 0);
	for (int i = 1; i <= n; i++) {
		cout << f[i] << "\n";
	}
}

Details

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

Test #1:

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

input:

1


output:

0

result:

ok 1 number(s): "0"

Test #2:

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

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: 11500kb

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: 11520kb

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: 0ms
memory: 11528kb

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: 3ms
memory: 11524kb

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: 92ms
memory: 16812kb

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: 27ms
memory: 15632kb

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: 56ms
memory: 16856kb

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: 42ms
memory: 16796kb

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