/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 2e5 + 10;
int n;
vector < int > adj[maxn];
void input()
{
cin >> n;
for (int i = 1; i < n; i ++)
{
int v, u;
cin >> v >> u;
adj[v].push_back(u);
adj[u].push_back(v);
}
}
int used[maxn], sub[maxn], init_sub[maxn];
void init_calc(int v, int p)
{
init_sub[v] = 1;
for (int u : adj[v])
{
if (u == p || used[u])
continue;
init_calc(u, v);
init_sub[v] += init_sub[u];
}
}
void calc(int v, int p)
{
sub[v] = 1;
for (int u : adj[v])
{
if (u == p || used[u])
continue;
calc(u, v);
sub[v] += sub[u];
}
}
int find_centroid(int v, int p, int sz)
{
for (int u : adj[v])
{
if (u == p || used[u])
continue;
if (sub[u] > sz / 2)
return find_centroid(u, v, sz);
}
return v;
}
int depth[maxn], temp_sub[maxn];
void make_data(int v, int p)
{
///cout << "make data " << v << " " << p << endl;
for (int u : adj[v])
{
if (used[u] || u == p)
continue;
depth[u] = depth[v] + 1;
if (init_sub[u] < init_sub[v])
temp_sub[u] = init_sub[u];
else
temp_sub[u] = n - init_sub[v];
make_data(u, v);
}
}
set < pair < int, int > > act;
int max_path[maxn];
void check(int v, int p, int gb)
{
int id = 2 * min(gb, temp_sub[v]);
max_path[id] = max(max_path[id], depth[v]);
pair < int, int > cur = {temp_sub[v], -1};
set < pair < int, int > > :: iterator it = act.lower_bound(cur);
if (it != act.end())
{
///cout << "check " << v << " " << it -> second << " " << depth[v] << endl;
max_path[2 * temp_sub[v]] = max(max_path[2 * temp_sub[v]], it -> second + depth[v]);
}
for (int u : adj[v])
{
if (used[u] || u == p)
continue;
check(u, v, gb);
}
}
void add(int v, int p)
{
pair < int, int > cur = {temp_sub[v], depth[v]};
set < pair < int, int > > :: iterator it = act.lower_bound(cur);
if (it == act.end() || it -> second < depth[v])
{
act.insert(cur);
while(true)
{
it = act.find(cur);
if (it == act.begin())
break;
it = prev(it);
if (it -> second <= depth[v])
act.erase(it);
else
break;
}
}
for (int u : adj[v])
{
if (used[u] || u == p)
continue;
add(u, v);
}
}
void decompose(int v)
{
calc(v, 0);
v = find_centroid(v, 0, sub[v]);
/// v is centroid
used[v] = 1;
make_data(v, 0);
///cout << "centroid " << v << endl;
for (int j = 0; j < adj[v].size(); j ++)
{
int u = adj[v][j];
if (used[u])
continue;
check(u, v, n - temp_sub[u]);
add(u, v);
}
act.clear();
reverse(adj[v].begin(), adj[v].end());
for (int j = 0; j < adj[v].size(); j ++)
{
int u = adj[v][j];
if (used[u])
continue;
check(u, v, n - temp_sub[u]);
add(u, v);
}
act.clear();
for (int u : adj[v])
{
if (!used[u])
{
decompose(u);
}
}
}
void solve()
{
input();
for (int i = 1; i <= n; i ++)
max_path[i] = -1;
decompose(1);
for (int i = n; i > 0; i --)
max_path[i] = max(max_path[i], max_path[i + 1]);
for (int i = 1; i <= n; i ++)
{
if (i % 2 == 1)
cout << 1 << endl;
else
cout << max_path[i] + 1 << endl;
}
}
int main()
{
speed();
solve();
return 0;
}
Compilation message
meetings2.cpp: In function 'void make_data(int, int)':
meetings2.cpp:89:9: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
89 | else
| ^~~~
meetings2.cpp:91:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
91 | make_data(u, v);
| ^~~~~~~~~
meetings2.cpp: In function 'void decompose(int)':
meetings2.cpp:157:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
157 | for (int j = 0; j < adj[v].size(); j ++)
| ~~^~~~~~~~~~~~~~~
meetings2.cpp:168:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
168 | for (int j = 0; j < adj[v].size(); j ++)
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9560 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
9564 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9560 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
9564 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9560 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
9564 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
