#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 200000 + 10;
const int MOD = 1e9 + 7;
int n;
struct SegmentTree
{
int tree[4 * MAXN];
void update(int l, int r, int node, int queryPos, int queryVal)
{
if (l == r)
{
if (queryVal == 0) tree[node] = queryVal;
else tree[node] = std::max(tree[node], queryVal);
return;
}
int mid = (l + r) / 2;
if (queryPos <= mid) update(l, mid, 2*node, queryPos, queryVal);
else update(mid + 1, r, 2*node + 1, queryPos, queryVal);
tree[node] = std::max(tree[2*node], tree[2*node + 1]);
}
int findMAX(int l, int r, int node, int queryL, int queryR)
{
if (queryL <= l && r <= queryR)
{
return tree[node];
}
int res = 0;
int mid = (l + r) / 2;
if (queryL <= mid) res = std::max(res, findMAX(l, mid, 2*node, queryL, queryR));
if (mid + 1 <= queryR) res = std::max(res, findMAX(mid + 1, r, 2*node + 1, queryL, queryR));
return res;
}
void update(int pos, int val)
{
update(1, n, 1, pos, val);
}
int findMAX(int l, int r)
{
return findMAX(1, n, 1, l, r);
}
};
int in[MAXN];
int sz[MAXN];
int szC[MAXN];
int par[MAXN];
int dep[MAXN];
int out[MAXN];
int answer[MAXN];
SegmentTree tree;
std::vector <int> g[MAXN];
std::vector <int> c[MAXN];
int timer;
void buildDFS(int node, int p)
{
par[node] = p;
for (int &u : g[node])
{
if (u == par[node])
{
std::swap(u, g[node].back());
break;
}
}
in[node] = ++timer;
sz[node] = 1;
for (const int &u : g[node])
{
if (u == par[node])
{
continue;
}
buildDFS(u, node);
sz[node] += sz[u];
}
out[node] = timer;
}
bool inSubtree(int x, int y)
{
return in[y] <= in[x] && out[x] <= out[y];
}
int getSubtree(int node, int root)
{
if (node == root)
{
return n;
}
if (!inSubtree(root, node))
{
return sz[node];
}
assert(g[node].size() >= 1 + (node != 1));
int l = 0, r = g[node].size() - (node != 1), mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (in[root] < in[g[node][mid]]) r = mid;
else l = mid;
}
assert(inSubtree(root, g[node][l]));
return n - sz[g[node][l]];
}
int ans[MAXN];
bool vis[MAXN];
int output[MAXN];
void calcSZ(int node, int par)
{
szC[node] = 1;
for (const int &u : g[node])
{
if (u == par || vis[u])
{
continue;
}
calcSZ(u, node);
szC[node] += szC[u];
}
}
int findCentroid(int node, int par, int size)
{
for (const int &u : g[node])
{
if (u == par || vis[u])
{
continue;
}
if (szC[u] > size / 2)
{
return findCentroid(u, node, size);
}
}
return node;
}
int decompose(int node, int d)
{
calcSZ(node, 0);
int cntr = findCentroid(node, 0, szC[node]);
vis[cntr] = true;
dep[cntr] = d;
for (const int &u : g[cntr])
{
if (vis[u])
{
continue;
}
c[cntr].push_back(decompose(u, d + 1));
}
return cntr;
}
void checkDFS(int node, int par, int dist, int lvl, int centroid)
{
int currSize = getSubtree(node, centroid);
int centroidSize = std::min(currSize, getSubtree(centroid, node));
ans[centroidSize] = std::max(ans[centroidSize], dist);
ans[currSize] = std::max(ans[currSize], dist + tree.findMAX(currSize, n));
for (const int &u : g[node])
{
if (dep[u] > lvl && u != par)
{
checkDFS(u, node, dist + 1, lvl, centroid);
}
}
}
void addDFS(int node, int par, int dist, int lvl, int centroid)
{
int currSize = getSubtree(node, centroid);
tree.update(currSize, dist);
for (const int &u : g[node])
{
if (dep[u] > lvl && u != par)
{
addDFS(u, node, dist + 1, lvl, centroid);
}
}
}
void resetDFS(int node, int par, int dist, int lvl, int centroid)
{
int currSize = getSubtree(node, centroid);
tree.update(currSize, 0);
for (const int &u : g[node])
{
if (dep[u] > lvl && u != par)
{
resetDFS(u, node, dist + 1, lvl, centroid);
}
}
}
void solveDFS(int node)
{
for (const int &u : c[node])
{
solveDFS(u);
}
for (int idx = 0 ; idx < g[node].size() ; ++idx)
{
int u = g[node][idx];
if (dep[u] < dep[node])
{
continue;
}
checkDFS(u, node, 1, dep[node], node);
addDFS(u, node, 1, dep[node], node);
}
for (const int &u : g[node])
{
resetDFS(u, node, 1, dep[node], node);
}
for (int idx = (int)g[node].size() - 1 ; idx >= 0 ; --idx)
{
int u = g[node][idx];
if (dep[u] < dep[node])
{
continue;
}
checkDFS(u, node, 1, dep[node], node);
addDFS(u, node, 1, dep[node], node);
}
for (const int &u : g[node])
{
resetDFS(u, node, 1, dep[node], node);
}
}
void solve()
{
buildDFS(1, 0);
int root = decompose(1, 1);
solveDFS(root);
for (int i = 1 ; i <= n ; ++i)
{
if (i & 1) output[i] = 1;
else output[i] = ans[i / 2] + 1;
}
}
void print()
{
for (int i = 1 ; i <= n ; ++i)
{
std::cout << output[i] << '\n';
}
}
void input()
{
std::cin >> n;
for (int i = 1 ; i < n ; ++i)
{
int u, v;
std::cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
print();
return 0;
}
/*
16 15
4 9
9 10
10 6
16 6
4 5
5 14
14 15
5 7
8 14
14 13
11 5
5 12
5 2
5 1
3 5
*/
Compilation message
meetings2.cpp: In function 'void solveDFS(int)':
meetings2.cpp:235:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
235 | for (int idx = 0 ; idx < g[node].size() ; ++idx)
| ~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16732 KB |
Output is correct |
| 2 |
Correct |
3 ms |
16732 KB |
Output is correct |
| 3 |
Correct |
3 ms |
16732 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
16732 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16732 KB |
Output is correct |
| 2 |
Correct |
3 ms |
16732 KB |
Output is correct |
| 3 |
Correct |
3 ms |
16732 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
16732 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16732 KB |
Output is correct |
| 2 |
Correct |
3 ms |
16732 KB |
Output is correct |
| 3 |
Correct |
3 ms |
16732 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
16732 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
