#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define task "coci2021_r1_papricice"
const int N = 2e5 + 5 ;
int n ;
vector<int> D[N] ;
void Inp()
{
cin >> n ;
for(int i = 1 ; i < n ; i++){
int u , v ;
cin >> u>> v;
D[u].push_back(v) ;
D[v].push_back(u) ;
}
}
namespace SUB2{
set<int> A , B ;
int cnt[N] ;
void dfs(int u , int p){
cnt[u] = 1 ;
for(int v : D[u]){
if(v == p) continue;
dfs(v , u) ;
cnt[u] += cnt[v] ;
}
}
int get_dif(int a , int b , int c){
return max({a , b , c}) - min({a , b , c}) ;
}
vector<int> get_result(const set<int>&A , int x){
vector<int> res ;
auto j = A.upper_bound(x) ;
if(j != A.end()) res.push_back(*j) ;
if(j != A.begin()) {
--j ;
res.push_back(*j) ;
}
return res ;
}
int dfs2(int u , int p){
int res = 1e9 ;
for(auto x : get_result(A , (n + cnt[u]) / 2)){
res = min(res , get_dif(n - x , cnt[u], x - cnt[u])) ;
}
for(auto x : get_result(B , (n - cnt[u]) / 2)){
res = min(res , get_dif(n - x - cnt[u] , x , cnt[u])) ;
}
A.insert(cnt[u]) ;
for(int v : D[u]){
if(v == p) continue;
res = min(res , dfs2(v , u)) ;
}
A.erase(cnt[u]) ;
B.insert(cnt[u]) ;
return res ;
}
void Solve(){
dfs(1 , 0) ;
cout << dfs2(1 , 0) ;
}
}
void Solve()
{
SUB2::Solve() ;
}
void Out()
{
}
int main()
{
ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
if(ifstream(task".INP")){
freopen(task".INP","r",stdin) ;
freopen(task".OUT","w",stdout) ;
}
Inp();
Solve();
Out();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
papricice.cpp: In function 'int main()':
papricice.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | freopen(task".INP","r",stdin) ;
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
papricice.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | freopen(task".OUT","w",stdout) ;
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |