#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define ALL(x) (x).begin(), (x).end()
const int MAXN = 200000;
int n;
vector<int> children[MAXN+5];
int sz[MAXN+5];
int best_diff;
// DFS 1: tính sz[u]
void dfs_sz(int u){
sz[u] = 1;
for(int v : children[u]){
dfs_sz(v);
sz[u] += sz[v];
}
}
// DFS 2: DSU on Tree, trả về con trỏ đến set của subtree u
set<pair<int,int>>* dfs_dsu(int u){
// tạo set mới và chèn chính u
auto *S = new set<pair<int,int>>();
S->insert(make_pair(sz[u], u));
// với mỗi con v, merge vào S
for(int v : children[u]){
auto *Sv = dfs_dsu(v);
// luôn gắn tập nhỏ vào tập lớn
if(S->size() < Sv->size()) swap(S, Sv);
// merge Sv vào S
for(auto &p : *Sv){
S->insert(p);
}
delete Sv;
}
// sau khi có S chứa mọi (sz[x], x) trong subtree u
// tìm candidate gần target = sz[u]/2
int target = sz[u] / 2;
auto it = S->lower_bound(make_pair(target, -1));
// kiểm tra it
vector<set<pair<int,int>>::iterator> cands;
if(it != S->end()) cands.push_back(it);
if(it != S->begin()){
auto it2 = it; --it2;
cands.push_back(it2);
}
// đánh giá từng ứng viên
for(auto itc : cands){
int sv = itc->first;
// phần thứ hai nếu cắt tại (u - itc->second)
int a = sv;
int b = sz[u] - sv;
int c = n - sz[u];
int mx = max(a, max(b,c));
int mn = min(a, min(b,c));
best_diff = min(best_diff, mx - mn);
}
return S;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
// đọc vào dạng cây có hướng từ 1 làm gốc
// giả sử input cho cạnh x-y, ta sẽ thêm y vào children[x] và ngược lại,
// nhưng cần root cây tại 1; ta chạy thêm một BFS/DFS để xác định parent→child.
vector<vector<int>> adj(n+1);
FOR(i,1,n-1){
int x,y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
// build children[] rooted tại 1
vector<int> stk; stk.reserve(n);
vector<bool> seen(n+1,false);
stk.push_back(1);
seen[1] = true;
for(int idx=0; idx < (int)stk.size(); ++idx){
int u = stk[idx];
for(int v : adj[u]){
if(!seen[v]){
seen[v] = true;
children[u].push_back(v);
stk.push_back(v);
}
}
}
// tính kích thước
dfs_sz(1);
// khởi best_diff lớn
best_diff = n;
// DSU on tree + tìm best cut thứ 2 cho mỗi u
auto *unused = dfs_dsu(1);
delete unused;
cout << best_diff << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |