UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#201414#3491. 最优选择FinderHT100726ms27800kbC++111.6kb2024-01-28 10:09:562024-01-28 12:09:26

answer

#include<bits/stdc++.h>
#define gt getchar
#define pt putchar
#define int long long
#define ull unsigned long long
#define fst first
#define snd second
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
typedef pair<int,int> pii;
const double eps=1e-6;
inline bool pts(char ch){return ch>=48&&ch<=57;}
inline int read(){
	bool f=0;int x=0;char ch;
	ch=gt();
	while(!pts(ch)&&ch!=EOF){if(ch=='-')f=1;ch=gt();}
	while(pts(ch)){x*=10;x+=(ch-48);ch=gt();}
	if(f)return -x;
	else return x;
}
template<class T>
inline void print(T x){
	char s[114];
	int top=0;
	if(x<0)pt('-');
	do{
		top++;
		if(x>=0)s[top]=(x%10)+48;
		else s[top]=(-(x%10)+48);
		x/=10;
	}while(x);
	while(top){pt(s[top]);top--;}
}
const int MAXN=3e5+10;
int sz[MAXN],d[MAXN],ans[MAXN];
int n,G,mxg=0x7fffffff;;
vector<int>g[MAXN];
void add_edge(int s,int e){
    g[s].push_back(e);
}
void dfs1(int x,int f){ 
    sz[x]=1;
    int mx=0;
    for(auto v:g[x]){
        if(v==f)continue; 
        dfs1(v,x);
        d[x]+=d[v]+sz[v];
        sz[x]+=sz[v];
        mx=max(mx,sz[v]);
    }
    mx=max(mx,n-sz[x]); 
    if(mx<mxg)G=x,mxg=mx;
}
void dfs2(int x,int f){
    ans[1]=d[1];
    for(auto v:g[x]){
        if(v==f)continue;
        ans[v]=ans[x]-sz[v]+n-sz[v];
        dfs2(v,x);
    } 
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++){
        int s=read(),e=read();
        add_edge(s,e);
        add_edge(e,s);
    }
    dfs1(1,0);
    dfs2(1,0);
    int sum=0;
    for(int i=1;i<=n;i++)
        if(i!=G)sum+=ans[i];
    cout<<sum-ans[G];
    return 0;
}

Details

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

Test #1:

score: 10
Accepted
time: 4ms
memory: 13496kb

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

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

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: 2ms
memory: 13696kb

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

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

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: 217ms
memory: 26216kb

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: 123ms
memory: 27784kb

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: 179ms
memory: 26224kb

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: 201ms
memory: 27800kb

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