ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#201400 | #3491. 最优选择 | I_am_kunzi | 100 | 757ms | 26060kb | C++ | 1.6kb | 2024-01-28 09:41:21 | 2024-01-28 12:07:37 |
answer
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<list>
#include<limits.h>
using namespace std;
vector < int > v[300005];
long long treesize[300005];
long long maxxtree = INT_MAX;
int g;
int n;
long long dis_tree[300005];
long long dis_all[300005];
void dfs(int nowx , int fa)
{
treesize[nowx] = 1;
long long maxxsize = 0;
for(int i = 0 ; i < v[nowx].size() ; i++)
{
if(v[nowx][i] == fa)
{
continue;
}
dfs(v[nowx][i] , nowx);
treesize[nowx] += treesize[v[nowx][i]];
dis_tree[nowx] += dis_tree[v[nowx][i]] + treesize[v[nowx][i]];
maxxsize = max(maxxsize , treesize[v[nowx][i]]);
}
maxxsize = max(maxxsize , n - treesize[nowx]);
if(maxxsize < maxxtree)
{
maxxtree = maxxsize;
g = nowx;
}
}
void calc_dis(int nowx , int fa)
{
for(int i = 0 ; i < v[nowx].size() ; i++)
{
if(v[nowx][i] == fa)
{
continue;
}
dis_all[v[nowx][i]] = dis_all[nowx] - treesize[v[nowx][i]] + (n - treesize[v[nowx][i]]);
calc_dis(v[nowx][i] , nowx);
}
}
signed main()
{
scanf("%d" , &n);
for(int i = 1 ; i < n ; i++)
{
int x , y;
scanf("%d%d" , &x , &y);
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1 , 0);
dis_all[1] = dis_tree[1];
calc_dis(1 , 0);
long long ans = 0;
for(int i = 1 ; i <= n ; i++)
{
if(i == g)
{
ans -= dis_all[i];
}
else
{
ans += dis_all[i];
}
}
cout << ans << endl;
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 3ms
memory: 13292kb
input:
300 295 292 73 103 205 68 183 162 15 24 154 115 111 35 138 281 126 147 174 287 280 25 28 69 90 80 24...
output:
2075896
result:
ok single line: '2075896'
Test #2:
score: 10
Accepted
time: 0ms
memory: 13292kb
input:
300 143 34 175 34 286 37 291 170 136 266 130 34 94 170 83 174 152 174 167 288 8 34 161 266 238 138 1...
output:
312592
result:
ok single line: '312592'
Test #3:
score: 10
Accepted
time: 4ms
memory: 13292kb
input:
300 228 198 203 282 103 203 152 283 273 122 292 132 69 125 188 82 280 196 286 8 121 145 207 223 168 ...
output:
2350364
result:
ok single line: '2350364'
Test #4:
score: 10
Accepted
time: 3ms
memory: 13496kb
input:
5000 1951 4165 836 450 4363 279 4766 3557 4243 989 1800 666 552 2706 1853 1377 2203 4090 4169 360 42...
output:
125904196
result:
ok single line: '125904196'
Test #5:
score: 10
Accepted
time: 0ms
memory: 13484kb
input:
5000 3104 1410 2883 4771 4271 2227 1426 4048 4505 4763 207 4625 2556 1573 4644 4325 357 1616 3918 13...
output:
1596577980
result:
ok single line: '1596577980'
Test #6:
score: 10
Accepted
time: 5ms
memory: 13496kb
input:
5000 4284 4090 2775 3341 2597 4048 3286 4927 2948 2124 2891 4948 2837 1831 976 4877 2365 1990 2077 3...
output:
129275764
result:
ok single line: '129275764'
Test #7:
score: 10
Accepted
time: 221ms
memory: 24804kb
input:
300000 104582 234120 292537 276357 198762 284891 179112 115090 62779 26517 188850 227557 214063 2553...
output:
18577987869700
result:
ok single line: '18577987869700'
Test #8:
score: 10
Accepted
time: 168ms
memory: 26052kb
input:
300000 236502 215399 74568 67877 148657 58296 286895 238209 258616 295461 80299 144986 10561 115692 ...
output:
660904179192
result:
ok single line: '660904179192'
Test #9:
score: 10
Accepted
time: 201ms
memory: 24796kb
input:
300000 84840 209344 63910 250801 256535 15383 284136 271103 158098 24328 161876 20374 7179 193692 25...
output:
17203414483972
result:
ok single line: '17203414483972'
Test #10:
score: 10
Accepted
time: 152ms
memory: 26060kb
input:
300000 250759 194662 232378 62498 86536 71427 281390 292867 147250 76358 5585 163671 83009 91839 405...
output:
659995157552
result:
ok single line: '659995157552'
Extra Test:
score: 0
Extra Test Passed