ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#201409 | #3491. 最优选择 | JuRuoError_YBW | 100 | 1729ms | 30176kb | C++11 | 1.2kb | 2024-01-28 09:57:28 | 2024-01-28 12:09:00 |
answer
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define int long long
char freadgetchar(){
static char buf[100000],*p1=buf,*p2=buf;
if(p1==p2){
p2=(p1=buf)+fread(buf,1,100000,stdin);
if (p1==p2)return EOF;
}
return *p1++;
}
void read(int&x){
static char c;
c=freadgetchar();
int b=1;
for(x = 0;!(c>='0'&&c<='9');c=freadgetchar()) if(c == '-') b = -b;
for(;c>='0'&&c<='9';x=x*10+c-'0',c=freadgetchar());x*=b;
}
const int MAXN=3e5+5;
std::vector<int> g[MAXN];
int n,ff[MAXN];
int G,mxg=1e18;
int sz[MAXN];
int d[MAXN],ans[MAXN];
void dfs1(int x,int fa){
sz[x]=1;
int mx=0;
for(auto v:g[x]){
if(v==fa)continue;
dfs1(v,x);
d[x]+=d[v]+sz[v];
sz[x]+=sz[v];
mx=std::max(mx,sz[v]);
}
mx=std::max(mx,n-sz[x]);
if(mx<mxg)G=x,mxg=mx;
}
void dfs2(int x,int f){
for(auto v:g[x]){
if(v==f)continue;
ans[v]=ans[x]-sz[v]+n-sz[v];
dfs2(v,x);
}
}
signed main(){
std::cin>>n;
for(int i=2;i<=n;i++){
int u,v;
std::cin>>u>>v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
dfs1(1,0);
ans[1]=d[1];
dfs2(1,0);
int sum=0;
for(int i=1;i<=n;i++){
sum+=ans[i];
//std::cout<<ans[i]<<'\n';
}
//std::cout<<G<<'\n';
std::cout<<sum-2*ans[G]<<'\n';
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 15620kb
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: 15624kb
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: 0ms
memory: 15624kb
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: 7ms
memory: 15856kb
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: 15836kb
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: 3ms
memory: 15860kb
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: 350ms
memory: 28600kb
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: 511ms
memory: 30168kb
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: 553ms
memory: 28600kb
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: 305ms
memory: 30176kb
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