#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
int n,ans = 1e9 + 7,subt[N];
vector < int > tree[N];
set < int > cont[N];
inline int eval(int a , int b , int c){
//printf("eval(%d,%d,%d) ",a,b,c);
return max({abs(a-b) , abs(a-c) , abs(b-c)});
}
inline int find_t1(int a1){
return (n - a1)/2;
}
inline int find_t2(int a1){
return (n - a1);
}
inline int closest_set(int tar , set < int > &ste){
auto hi = ste.lower_bound(tar);
auto lo = --ste.lower_bound(tar);
if(hi == ste.end())return *lo;
else if(hi == ste.begin())return *hi;
else if(abs(tar-*hi) < abs(tar-*lo))return *hi;
else return *lo;
}
inline int closest_vec(int tar , deque < int > &vec){
auto hi = lower_bound(vec.begin() , vec.end() , tar);
auto lo = --lower_bound(vec.begin() , vec.end() , tar);
if(hi == vec.end())return *lo;
else if(hi == vec.begin())return *hi;
else if(abs(tar-*hi) < abs(tar-*lo))return *hi;
else return *lo;
}
inline void dfs0(int node , int past){
subt[node] = 1;
for(auto itr : tree[node]){
if(itr != past){
dfs0(itr,node);
subt[node] += subt[itr];
}
}
}
inline void dfs1(int node , int past){
if(tree[node].size() == 1 and past != 0){//leaf ise
cont[node].insert(1);
return;
}
vector < int > cand;
int mxnode = -1;
for(auto itr : tree[node]){
if(itr != past){
dfs1(itr,node);
cand.push_back(itr);
if(mxnode == -1 or subt[mxnode] < subt[itr])mxnode = itr;
}
}
cand.erase(find(cand.begin() , cand.end() , mxnode));
//cout << "node : " << node << endl;
for(auto itr : cand){
for(auto itr1 : cont[itr]){
int itr2 = closest_set(find_t1(itr1),cont[mxnode]);
// cout << "dfs1 - " << node << " " << itr1 << " " << itr2 << endl;
ans = min(ans , eval(n-itr1-itr2,itr1,itr2));
cont[mxnode].insert(itr1);
}
cont[itr].clear();
}
cont[node].swap(cont[mxnode]);
cont[node].insert(subt[node]);
}
deque < int > path;
inline void dfs2(int node , int past){
if(path.size() > 1){
//cout << "optimal : " << find_t2(subt[node]) << endl;
//cout << "node : ";for(auto itr : path)cout << itr << " ";cout << endl;
int itr1 = subt[node] , itr2 = closest_vec(find_t2(subt[node]),path);
//cout << "dfs2 : " << node << " , " << itr1 << " , " << itr2 << " = " << eval(n-itr2,itr2-itr1,itr1) << endl;
ans = min(ans , eval(n-itr2,itr2-itr1,itr1));
}
for(auto itr : tree[node]){
if(itr != past){
path.push_front(subt[node]);
dfs2(itr,node);
path.pop_front();
}
}
}
void solve(){
cin >> n;
for(int i = 1;i<n;i++){
int u,v;cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}
//precalc : subtree size
dfs0(1,0);
//small to large ile disjoint setlerin cevabını bul
dfs1(1,0);
//cout << "dfs1 : " << ans << endl;
//bs ile iç içe setlerin cevabını bul
dfs2(1,0);
//cout << "dfs2 : " << ans << endl;
cout << ans << endl;
}
signed main(){
//ios_base::sync_with_stdio(0);cin.tie(0);
int testcase = 1;//cin >> testcase;
while(testcase--)solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
14940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
14940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
14940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
