#include <bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int i = (a), _b = b;i <= _b; i++) #define FORD(i,a,b) for(int i = (a), _b = b;i >= _b; i--) #define int long long #define fi first #define se second #define pb push_back #define all(x) x.begin(),x.end() #define mp make_pair #define task "hhung" template<class x,class y> bool minimize(x &a,const y &b){ if(a > b){ a = b; return true; }else return false; } template<class x,class y> bool maximize(x &a,const y &b){ if(a < b){ a = b; return true; }else return false; } typedef pair<int,int> pii; constexpr int MAXN=1e6,MOD=1e9+7,INF=1e18; int n,m,l,r,k,ans,res; vector<int> adj[MAXN]; multiset<int> s1,s2; int de[MAXN]; void dfs(int u,int p){ de[u] = 1; for(int v : adj[u]){ if(v != p){ dfs(v,u); de[u] += de[v]; } } } void dfs1(int u,int p){ auto idx = s1.upper_bound((n + de[u])/2); if(idx != s1.end()){ int a = de[u]; int b = *idx - de[u]; int c = n - *idx; minimize(ans,max({a,b,c}) - min({a,b,c})); } if(idx != s1.begin()){ --idx; int a = de[u]; int b = *idx - de[u]; int c = n - *idx; minimize(ans,max({a,b,c}) - min({a,b,c})); } s1.insert(de[u]); for(int v : adj[u]){ if(v != p){ dfs1(v,u); } } s1.erase(s1.find(de[u])); } void dfs2(int u,int p){ auto idx = s2.upper_bound((n - de[u])/2); if(idx != s2.end()){ int a = de[u]; int b = *idx - de[u]; int c = n - *idx; minimize(ans,max({a,b,c}) - min({a,b,c})); } if(idx != s2.begin()){ --idx; int a = de[u]; int b = *idx - de[u]; int c = n - *idx; minimize(ans,max({a,b,c}) - min({a,b,c})); } for(int v : adj[u]){ if(v != p){ dfs2(v,u); } } s2.insert(de[u]); } int32_t main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); if(fopen(task".inp","r")){ freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } cin >> n ; FOR(i,1,n-1){ int u,v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } ans = INF; dfs(1,0); dfs1(1,0); dfs2(1,0); cout << ans; }

papricice.cpp: In function 'int32_t main()':
papricice.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
papricice.cpp:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~