#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pi;
typedef pair<ll, pair<ll, ll> > pii;
typedef vector <ll> vi;
#define forw(i,a,b) for (ll i=a;i<=(b);i++)
#define forb(i,a,b) for (ll i=a;i>=(b);i--)
#define fast {ios::sync_with_stdio(false); cin.tie(0); }
#define fi first
#define se second
#define pu push
#define puf push_front
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fr front
#define all(a) a.begin(),a.end()
const ll oo=1e18;
const ll mod=1e9+7;
const int base=31;
const int tx[4]={0,0,1,-1};
const int ty[4]={1,-1,0,0};
const ll maxN=2e5+5;
set<int> save[maxN];
vector <int> check[maxN];
int n,ans,sum[maxN];
void dfs(int u, int father)
{
sum[u]=1;
int res=1;
for(int v:check[u])
if (v!=father)
{
dfs(v,u);
int top,bot,mid;
top=n-sum[v];
int x=(n-top)/2+((n-top)%2);
auto it=save[v].lower_bound(x);
if (it!=save[v].end())
{
bot=*it;
mid=n-top-bot;
if (mid!=0 && bot!=0 && top!=0)
ans=min(ans,max(mid,max(top,bot))-min(mid,min(top,bot)));
}
if (it!=save[v].begin())
{
it--;
bot=*it;
mid=n-top-bot;
if (mid!=0 && bot!=0 && top!=0)
ans=min(ans,max(mid,max(top,bot))-min(mid,min(top,bot)));
}
if (it!=save[v].begin())
{
it--;
bot=*it;
mid=n-top-bot;
if (mid!=0 && bot!=0 && top!=0)
ans=min(ans,max(mid,max(top,bot))-min(mid,min(top,bot)));
}
res=max(res,sum[v]);
sum[u]+=sum[v];
save[v].clear();
}
forw(i,1,res)
save[u].insert(i);
save[u].insert(sum[u]);
return;
}
void solve()
{
cin>>n;
forw(i,1,n-1)
{
int u,v;
cin>>u>>v;
check[u].pb(v);
check[v].pb(u);
}
int s=0;
ans=1e9;
forw(i,1,n)
if (check[i].size()==1)
{
s=i;
break;
}
dfs(s,0);
cout<<ans<<endl;
}
int main()
{
fast;
//freopen("test.inp","r",stdin);
//freopen("test.out","w",stdout);
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
14412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
14412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
14412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
