#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxN = 2e5 + 5;
const int logN = log2(maxN)+1;
vector<int> adj[maxN];
int parent[logN][maxN], sz[maxN], depth[maxN];
int c[maxN];
void dfs(int curNode, int prvNode, int d = 1){
parent[0][curNode] = prvNode;
for(int x=1;x<logN;x++){
parent[x][curNode] = parent[x-1][parent[x-1][curNode]];
}
sz[curNode] = 1;
c[curNode] = 0;
depth[curNode] = d;
for(auto nxt : adj[curNode]){
if(nxt != prvNode){
dfs(nxt, curNode, d+1);
}
}
}
void dfs2(int curNode, int prvNode){
for(auto nxt : adj[curNode]){
if(nxt != prvNode){
dfs2(nxt, curNode);
c[curNode] += (c[nxt] != 0);
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for(int x=0;x<n-1;x++){
int a, b;
cin >> a >> b;
a--; b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(0, 0);
pair<int, int> mx = {-1, -1};
for(int x=0;x<n;x++){
mx = max(mx, {depth[x], x});
}
dfs(mx.second, mx.second);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
multiset<int> st;
int cnt[n];
fill(cnt, cnt+n, 0);
fill(c, c+n, 0);
for(int x=0;x<n;x++){
if(adj[x].size() == 1 && (depth[x] == mx.first || depth[x] == 1)){
pq.push({1, x});
st.insert(1);
c[x] = 1;
sz[x] = 1;
cnt[x] = 1;
}
}
dfs2(mx.second, mx.second);
for(int x=0;x<n;x++){
if(depth[x] != 1){
c[x]++;
}
}
int d[n];
fill(d, d+n, 1);
for(int x=1;x<=n;x++){
if(x&1){
cout << "1\n";
} else {
while(!pq.empty() && pq.top().first < x/2){
int curNode = pq.top().second;
st.erase(st.find(d[curNode]));
pq.pop();
// cout << "- " << curNode << "\n";
int par = -1;
for(auto nxt : adj[curNode]){
// cout << nxt << " = " << cnt[nxt] << " " << c[nxt] << "\n";
if(cnt[nxt]+1 < c[nxt]){
par = nxt;
break;
}
}
if(par == -1) continue;
cnt[par]++;
if(cnt[par]+1 == c[par]){
sz[par] = 1;
for(auto nxt : adj[par]){
// cout << "nxt is " << nxt << " -> " << cnt[nxt] << " " << c[nxt] << " " << sz[nxt] << "\n";
if(cnt[nxt]+1 == c[nxt]){
sz[par] += sz[nxt];
}
}
// cout << "+ " << par << " " << sz[par] << "\n";
pq.push({sz[par], par});
d[par] = d[curNode]+1;
st.insert(d[par]);
}
}
int mn1 = -1, mn2 = -1;
for(auto val : st){
// cout << " = " << val << "\n";
if(mn1 == -1){
mn1 = val;
} else if(mn2 == -1){
mn2 = val;
} else {
break;
}
}
assert(mn1 != -1 && mn2 != -1);
cout << mx.first-mn1-mn2+2 << "\n";
}
}
// cout << diameter << " --\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5076 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
5076 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5076 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
5076 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5076 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
5076 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
