ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#197484 | #2732. 8.4t2 | tkswls | 100 | 220ms | 16856kb | C++11 | 1.6kb | 2023-11-12 11:47:38 | 2023-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