ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#197485 | #2732. 8.4t2 | snow_trace | 100 | 685ms | 48720kb | C++11 | 2.0kb | 2023-11-12 11:47:39 | 2023-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;
}
详细
小提示:点击横条可展开更详细的信息
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