#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll,ll>
#define mp make_pair
#define pb push_back
#define BIT(x,i) (((x)>>(i))&1)
#define MASK(i) (1LL<<(i))
template<typename T1, typename T2> bool minimize(T1 &a, T2 b)
{if(a>b) a=b; else return 0; return 1;}
template<typename T1, typename T2> bool maximize(T1 &a, T2 b)
{if(a<b) a=b; else return 0; return 1;}
#define file "task"
const int maxn = 2e5 + 5;
const int MOD = 1e9 + 7;
const int oo = 1e9;
const ll OO = 1e18;
int n;
int sz[maxn];
int ans = oo;
vector<int> g[maxn];
set<int> ancestor;
set<int> s[maxn];
int max(int a, int b, int c){
return max(max(a, b), c);
}
int min(int a, int b, int c){
return min(min(a, b), c);
}
void input(){
cin >> n;
for(int i = 1; i <= n - 1; i++){
int u, v; cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
}
void prep(int u, int dad){
sz[u] = 1;
for(int v : g[u]){
if(v == dad) continue;
prep(v, u);
sz[u] += sz[v];
}
}
void get(set<int> &s, int w){
int sum = n - w;
auto it = s.lower_bound(sum / 2);
if(it != s.end()){
minimize(ans, max(w, (*it), sum - (*it)) - min(w, (*it), sum - (*it)));
}
if(it != s.begin()){
it--;
minimize(ans, max(w, (*it), sum - (*it)) - min(w, (*it), sum - (*it)));
}
}
void dfs(int v, int dad){
for(int u : g[v]){
if(u == dad) continue;
dfs(u, v);
//dsu on tree
if(s[u].size() > s[v].size()) swap(s[u], s[v]);
for(int w : s[u]){
get(s[v], w);
}
for(int w : s[u]){
s[v].insert(w);
}
}
get(s[v], n - sz[v]);
s[v].insert(sz[v]);
}
void proc(){
ans = oo;
prep(1, 1);
dfs(1, 1);
cout << ans;
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(0); cout.tie(nullptr);
if(fopen(file".inp", "r")){
freopen(file".inp", "r", stdin);
freopen(file".out", "w", stdout);
}
input();
proc();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
papricice.cpp: In function 'int main()':
papricice.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
102 | freopen(file".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
papricice.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | freopen(file".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... |