#include <bits/stdc++.h>
#define se second
#define fs first
#define mp make_pair
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const int N = 2e5 + 7;
const int Mod = 1e9 + 7;
const int szBL = 320;
const int INF = 1e9;
const int BASE = 1337;
int n;
vector<int> ke[N];
namespace sub5 {
inline void maximize (int &a, int b) { if (a < b) a = b; }
int m;
int a[N];
int Ans[N];
bool del[N];
int nChild[N];
struct Segment_Tree {
int m;
int st[N << 2];
void init (int n) {
m = n;
rep (i, 1, m << 2) st[i] = -INF;
}
void update (int id, int l, int r, int pos, int val) {
if (l > pos || r < pos) return;
if (l == r) {
if (val == -INF) st[id] = val;
else st[id] = max(st[id], val);
return;
}
int mid = l + r >> 1;
update (id << 1, l, mid, pos, val);
update (id << 1 | 1, mid + 1, r, pos, val);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
int get (int id, int l, int r, int u, int v) {
if (l > v || r < u) return -INF;
if (l >= u && r <= v)
return st[id];
int mid = l + r >> 1;
return max(get (id << 1, l, mid, u, v), get (id << 1 | 1, mid + 1, r, u, v));
}
void update (int pos, int val) {
update (1, 1, m, pos, val);
}
int get (int u, int v) {
return get (1, 1, m, u, v);
}
}ST;
void pdfs (int u, int p) {
nChild[u] = 1;
iter (&v, ke[u]) {
if (v != p && !del[v]) {
pdfs (v, u);
nChild[u] += nChild[v];
}
}
}
int get_cen (int u, int p, int tot) {
iter (&v, ke[u]) {
if (v != p && !del[v] && nChild[v] >= tot / 2)
return get_cen(v, u, tot);
}
return u;
}
void dfs (int u, int p, int typ, int Dist = 1) {
if (typ == 1) ST.update (nChild[u], Dist);
else if(typ == 3) ST.update (nChild[u], -INF);
else {
maximize (Ans[nChild[u]], Dist + ST.get(nChild[u], n) + 1);
}
iter (&v, ke[u]) {
if (v != p && !del[v]) {
dfs (v, u, typ, Dist + 1);
}
}
}
void Clear (int u) {
iter (&v, ke[u]) if (!del[v]) dfs (v, u, 3);
}
void cen_dcps (int root) {
pdfs (root, 0);
int cen = get_cen (root, 0, nChild[root]);
pdfs (cen, 0);
iter (&v, ke[cen]) {
if (!del[v]) {
dfs (v, cen, 0);
dfs (v, cen, 1);
}
}
Clear(cen);
reb (i, SZ(ke[cen]) - 1, 0) {
int v = ke[cen][i];
if (!del[v]) {
dfs (v, cen, 0);
dfs (v, cen, 1);
}
}
Clear(cen);
iter (&v, ke[cen]) {
if (!del[v]) {
dfs (v, cen, 1);
int delta = nChild[cen] - nChild[v];
maximize(Ans[delta], ST.get (delta, n) + 1);
dfs (v, cen, 3);
ST.update (delta, 0);
dfs (v, cen, 0);
ST.update (delta, -INF);
}
}
del[cen] = 1;
iter (&v, ke[cen]) {
if (!del[v]) {
cen_dcps(v);
}
}
}
void solution() {
ST.init(n);
rep (i, 1, n + 1) Ans[i] = 1;
cen_dcps(1);
reb (i, n, 1) maximize(Ans[i], Ans[i + 1]);
rep (i, 1, n) {
if (i & 1) {
cout << 1 <<"\n";
}
else {
cout << Ans[i / 2] <<"\n";
}
}
}
}
namespace sub1 {
const ll N1 = 20;
int Dist[N1][N1];
void dfs (int root, int u, int p, int Dst = 0) {
Dist[root][u] = Dst;
iter (&v, ke[u]) {
if (v != p) {
dfs (root, v, u, Dst + 1);
}
}
}
void solution () {
rep (i, 1, n) dfs (i, i, 0);
rep (k, 1, n) {
int res = 0;
rep (msk, 1, (1 << n) - 1) {
if (__builtin_popcount(msk) != k) continue;
vector<int> vec;
rep (i, 1, n) if (bit(msk, i - 1)) vec.push_back(i);
int mnvl = INF, de = 0;
rep (i, 1, n) {
int cur = 0;
iter (&id, vec) cur += Dist[id][i];
if (cur < mnvl) {
de = 1;
mnvl = cur;
}
else if (cur == mnvl) ++de;
}
res = max(res, de);
}
cout << res<<"\n";
}
}
}
void solution () {
cin >> n;
rep (i, 1, n - 1) {
int u, v;
cin >> u >> v;
ke[u].push_back(v);
ke[v].push_back(u);
}
// pdfs(1, 0);
// if (n <= 16) sub1 :: solution();
// else
sub5 :: solution();
// rep (i, 1, n) {
// if (i & 1) cout << 1 <<"\n";
// else {
// cout << Diameter <<"\n";
// Diameter -= 2;
// }
// }
}
#define file(name) freopen(name".inp", "r", stdin); \
freopen(name".out", "w", stdout);
int main () {
file("c");
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll num_Test = 1;
// cin >> num_Test;
while(num_Test--)
solution();
}
/*
nếu mình nghĩ sẽ thay đổi định nghĩa, kiểu dữ liệu của hàm hay mảng j thì mình phải nghĩ xem nó sẽ ảnh hưởng đến các phần nào
5 10
798981764 -961045489
-762214604 -6816243
549909709 362471127
504233152 -881315415
503023672 -79630788
*/
Compilation message
meetings2.cpp: In member function 'void sub5::Segment_Tree::update(int, int, int, int, int)':
meetings2.cpp:56:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
56 | int mid = l + r >> 1;
| ~~^~~
meetings2.cpp: In member function 'int sub5::Segment_Tree::get(int, int, int, int, int)':
meetings2.cpp:65:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | int mid = l + r >> 1;
| ~~^~~
meetings2.cpp: In function 'void sub1::solution()':
meetings2.cpp:184:46: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
184 | rep (i, 1, n) if (bit(msk, i - 1)) vec.push_back(i);
| ~~^~~
meetings2.cpp:11:34: note: in definition of macro 'bit'
11 | #define bit(msk, i) ((msk >> i) & 1)
| ^
meetings2.cpp: In function 'int main()':
meetings2.cpp:223:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
223 | #define file(name) freopen(name".inp", "r", stdin); \
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
meetings2.cpp:227:5: note: in expansion of macro 'file'
227 | file("c");
| ^~~~
meetings2.cpp:224:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
224 | freopen(name".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
meetings2.cpp:227:5: note: in expansion of macro 'file'
227 | file("c");
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
