이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
int n;
int sz[MAXN], ans[MAXN], H[MAXN], nw[MAXN];
bool Mark[MAXN];
vector <int> Adj[MAXN];
void DFS(int node, int p)
{
sz[node] = 1;
for(auto x : Adj[node])
{
if(x == p or Mark[x])
{
continue;
}
DFS(x, node);
sz[node] += sz[x];
}
}
int FindCen(int node, int p, int cursz)
{
for(auto x : Adj[node])
{
if(x == p or Mark[x])
{
continue;
}
if(2 * sz[x] > cursz)
{
return FindCen(x, node, cursz);
}
}
return node;
}
vector <int> Cur;
void Cal(int node, int p)
{
sz[node] = 1;
for(auto x : Adj[node])
{
if(x == p or Mark[x])
{
continue;
}
H[x] = H[node] + 1;
Cal(x, node);
sz[node] += sz[x];
}
if(Cur.empty() or Cur[0] < sz[node])
{
// do nothing
}
else
{
int id = upper_bound(Cur.begin(), Cur.end(), sz[node], greater <int> ()) - Cur.begin() - 1;
assert(id >= 0);
ans[2 * sz[node]] = max(ans[2 * sz[node]], H[node] + id + 3);
}
nw[H[node]] = max(nw[H[node]], sz[node]);
}
void Cal2(int node, int p, int s)
{
for(auto x : Adj[node])
{
if(x == p or Mark[x])
{
continue;
}
Cal2(x, node, s);
}
if(Cur.empty() or Cur[0] < sz[node])
{
// do nothing
}
else
{
int id = upper_bound(Cur.begin(), Cur.end(), sz[node], greater <int> ()) - Cur.begin() - 1;
assert(id >= 0);
ans[2 * sz[node]] = max(ans[2 * sz[node]], H[node] + id + 3);
}
nw[H[node]] = max(nw[H[node]], sz[node]);
ans[2 * min(s, sz[node])] = max(ans[2 * min(s, sz[node])], H[node] + 2);
}
void Solve(int node, int p)
{
DFS(node, p);
int cen = FindCen(node, p, sz[node]);
Mark[cen] = true;
Cur.clear();
int ss = sz[node];
for(auto x : Adj[cen])
{
H[x] = 0;
if(Mark[x])
{
continue;
}
Cal(x, cen);
for(int i = 0; ; i++)
{
if(nw[i] == 0)
{
break;
}
if(i < (int)Cur.size())
{
Cur[i] = max(Cur[i], nw[i]);
}
else
{
Cur.push_back(nw[i]);
}
nw[i] = 0;
}
}
Cur.clear();
reverse(Adj[cen].begin(), Adj[cen].end());
for(auto x : Adj[cen])
{
H[x] = 0;
if(Mark[x])
{
continue;
}
Cal2(x, cen, ss - sz[x]);
for(int i = 0; ; i++)
{
if(nw[i] == 0)
{
break;
}
if(i < (int)Cur.size())
{
Cur[i] = max(Cur[i], nw[i]);
}
else
{
Cur.push_back(nw[i]);
}
nw[i] = 0;
}
}
for(auto x : Adj[cen])
{
if(!Mark[x])
{
Solve(x, cen);
}
}
}
int main()
{
// freopen("Input.txt", "r", stdin);
// freopen("Output2.txt", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
Adj[u].push_back(v);
Adj[v].push_back(u);
}
Solve(1, -1);
for(int i = n; i >= 1; i--)
{
ans[i] = max(ans[i], ans[i + 1]);
}
for(int i = 1; i <= n; i++)
{
if(i & 1)
{
cout << 1 << '\n';
}
else
{
cout << max(ans[i], 1) << '\n';
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |