#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 ll INF = 2e9;
const int BASE = 1337;
int n;
vector<int> ke[N];
namespace sub5 {
int m;
int nChild[N], par[N], high[N], pre[N];
int a[N];
int Ans[N];
void pdfs (int u, int p) {
nChild[u] = 1;
par[u] = p;
high[u] = high[p] + 1;
iter (&v, ke[u]) {
if (v != p) {
pdfs (v, u);
nChild[u] += nChild[v];
}
}
}
inline void maximize (int &a, int b) { if (a < b) a = b; }
vector<pair<int,int>> vec;
void dfs (int u, int p) {
int up;{
int lf = 0, rt = SZ(vec) - 1;
while (lf < rt) {
int mid = lf + rt >> 1;
if (vec[mid].fs >= nChild[u]) rt = mid;
else lf = mid + 1;
}
if (!vec.empty() && vec[lf].fs >= nChild[u]) up = lf;
else up = SZ(vec);
}
if (up != SZ(vec)) {
maximize(Ans[nChild[u]], high[u] - vec[up].se + 1);
}
--up;
if (!vec.empty() && up >= 0) {
maximize(Ans[vec[up].fs], high[u] - vec[up].se + 1);
}
iter (&v, ke[u]) {
if (v != p) {
pre[u] = pre[p] + nChild[u] - nChild[v];
vec.push_back(mp(pre[u], high[u]));
dfs (v, u);
vec.pop_back();
}
}
}
void solution() {
pdfs (1, 0);
rep (i, 1, n + 1) Ans[i] = 1;
dfs (1, 0);
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 function 'void sub5::dfs(int, int)':
meetings2.cpp:56:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
56 | int mid = lf + rt >> 1;
| ~~~^~~~
meetings2.cpp: In function 'void sub1::solution()':
meetings2.cpp:117:46: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
117 | 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)
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
