#include <iostream>
#include <vector>
#include <queue>
#include <array>
#include <map>
#define ll long long
using namespace std;
vector <ll> adj[200000];
bool C[200000];
vector <array<ll, 2>> U;
vector <ll> V[200000];
vector <vector<ll>> D;
ll n, k, a, b, cnt, f = 1e18, sz[200000], F[200000];
struct SegTree{
vector <ll> st{vector <ll> (800000, -1e18)};
vector <ll> updated;
void update(ll id, ll l, ll r, ll q, ll w) {
updated.push_back(id);
if (l == r) {
st[id] = max(st[id], w);
return;
}
ll mid = (l+r)/2;
if (q <= mid) update(id*2, l, mid, q, w);
else update(id*2+1, mid+1, r, q, w);
st[id] = max(st[id*2], st[id*2+1]);
}
ll query(ll id, ll l, ll r, ll q) {
if (r < q) return -1e18;
if (q <= l) return st[id];
ll mid = (l+r)/2;
return max(query(id*2, l, mid, q), query(id*2+1, mid+1, r, q));
}
void rollback() {
while (!updated.empty()) {
auto id = updated.back();
updated.pop_back();
st[id] = -1e18;
}
}
}ST;
void dfs_sz(ll u, ll p) {
sz[u] = 1;
for (auto v : adj[u]) {
if (v != p && !C[v]) {
dfs_sz(v, u);
sz[u] += sz[v];
}
}
}
ll find_cent(ll u, ll p, ll tot) {
ll mx = -1, ret = -1;
for (auto v : adj[u]) {
if (v != p && !C[v]) {
ret = max(ret, find_cent(v, u, tot));
mx = max(mx, sz[v]);
}
}
mx = max(mx, tot-sz[u]);
if (mx <= tot/2) return u;
else return ret;
}
void dfs_resz(ll u, ll p, ll w, ll x) {
if (D[x].size() == w) D[x].push_back(0);
sz[u] = 1;
for (auto v : adj[u]) {
if (v != p && !C[v]) {
dfs_resz(v, u, w+1, x);
sz[u] += sz[v];
}
}
D[x][w] = max(D[x][w], sz[u]);
}
void solve(ll u) {
dfs_sz(u, -1);
ll cent = find_cent(u, -1, sz[u]), z;
C[cent] = 1;
map <ll, ll> mp;
D.clear();
ll x = 0;
for (auto v : adj[cent]) {
if (!C[v]) {
D.push_back({});
dfs_resz(v, u, 0, x);
for (int i=0; i<D[x].size(); ++i) {
F[D[x][i]-1] = max(F[D[x][i]-1], ST.query(1, 0, n-1, D[x][i]-1) + i + 3);
}
for (int i=0; i<D[x].size(); ++i) {
ST.update(1, 0, n-1, D[x][i]-1, i);
}
++x;
}
}
ST.rollback();
while (x--) {
for (int i=0; i<D[x].size(); ++i) {
F[D[x][i]-1] = max(F[D[x][i]-1], ST.query(1, 0, n-1, D[x][i]-1) + i + 3);
}
for (int i=0; i<D[x].size(); ++i) {
ST.update(1, 0, n-1, D[x][i]-1, i);
}
}
ST.rollback();
for (auto v : adj[cent]) {
if (!C[v]) solve(v);
}
}
int main() {
cin >> n;
for (int i=0; i<n-1; ++i) {
cin >> a >> b;
--a, --b;
adj[a].push_back(b);
adj[b].push_back(a);
}
solve(0);
for (int i=n-2; i>=0; --i) {
F[i] = max(F[i], F[i+1]);
}
for (int i=0; i<n; ++i) {
if (!(i & 1)) cout << "1\n";
else cout << max(2LL, F[i/2]) << '\n';
}
}
Compilation message
meetings2.cpp: In function 'void dfs_resz(long long int, long long int, long long int, long long int)':
meetings2.cpp:70:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
70 | if (D[x].size() == w) D[x].push_back(0);
| ~~~~~~~~~~~~^~~~
meetings2.cpp: In function 'void solve(long long int)':
meetings2.cpp:92:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for (int i=0; i<D[x].size(); ++i) {
| ~^~~~~~~~~~~~
meetings2.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for (int i=0; i<D[x].size(); ++i) {
| ~^~~~~~~~~~~~
meetings2.cpp:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for (int i=0; i<D[x].size(); ++i) {
| ~^~~~~~~~~~~~
meetings2.cpp:106:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for (int i=0; i<D[x].size(); ++i) {
| ~^~~~~~~~~~~~
meetings2.cpp:83:38: warning: unused variable 'z' [-Wunused-variable]
83 | ll cent = find_cent(u, -1, sz[u]), z;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
19008 KB |
Output is correct |
| 2 |
Correct |
4 ms |
19036 KB |
Output is correct |
| 3 |
Correct |
4 ms |
19036 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
19036 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
19008 KB |
Output is correct |
| 2 |
Correct |
4 ms |
19036 KB |
Output is correct |
| 3 |
Correct |
4 ms |
19036 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
19036 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
19008 KB |
Output is correct |
| 2 |
Correct |
4 ms |
19036 KB |
Output is correct |
| 3 |
Correct |
4 ms |
19036 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
19036 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
