#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
vector<int> gr[N];
set<int> auxgr[N];
struct helpertime{
int nod, dad;
int sz;
};
int sz[N];
priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> leafs;
vector<helpertime> ht;
int ans[N];
int par[20][N];
int in[N], out[N];
int h[N];
void dfs_prec(int nod, int dad, int &cnt){
h[nod] = h[dad] + 1;
in[nod] = ++cnt;
par[0][nod] = dad;
for(int i = 1; i < 20; i ++)
par[i][nod] = par[i - 1][par[i - 1][nod]];
for(auto x:gr[nod]){
if(x == dad)
continue;
dfs_prec(x, nod, cnt);
}
out[nod] = cnt;
}
bool is_dad(int dad, int son){
if(in[dad] <= in[son] && out[son] <= out[dad])
return true;
return false;
}
int get_dist(int a, int b){
if(h[a] > h[b])
swap(a, b);
if(is_dad(a, b))
return h[b] - h[a] + 1;
int lca = a;
for(int p2 = 19; p2>=0; p2--){
int up = par[p2][lca];
if(up != 0 && is_dad(up, b) == false)
lca = up;
}
lca = par[0][lca];
return h[a] - h[lca] + 1 + h[b] - h[lca];
}
int main()
{
//freopen(".in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n;
cin>>n;
for(int i = 1; i<n; i++){
int x, y;
cin>>x>>y;
gr[x].push_back(y);
gr[y].push_back(x);
auxgr[x].insert(y);
auxgr[y].insert(x);
}
for(int i = 1; i<=n; i++){
sz[i] = 1;
}
for(int i = 1; i<=n; i++){
if(auxgr[i].size() == 1){
leafs.push({sz[i], i});
}
}
for(int t = 2; t <= (n + 1)/2; t++){
while(leafs.size() && leafs.top().first < t){
int nod = leafs.top().second;
leafs.pop();
if(auxgr[nod].size()){
assert(auxgr[nod].size() == 1);
int vec = *auxgr[nod].begin();
auxgr[nod].erase(vec);
auxgr[vec].erase(nod);
sz[vec] += sz[nod];
ht.push_back({nod, vec, sz[nod]});
if(auxgr[vec].size() == 1){
leafs.push({sz[vec], vec});
}
}
else{
cerr<<"-1\n";
}
}
}
int cnt = 0;
dfs_prec(1, 0, cnt);
int root = 0;
for(int i = 1; i<=n; i++)
if(sz[i] == n)
root = i;
int diama = root, diamb = root;
int dst = 1;
for(int t = n/2; t>=1; t--){
while(ht.size() && ht.back().sz >= t){
int newnod = ht.back().nod;
int dstna = get_dist(diama, newnod);
int dstnb = get_dist(diamb, newnod);
if(dstna > dst && dstna >= dstnb){
dst = dstna;
diamb = newnod;
}
else if(dstnb > dst && dstnb >= dstna){
dst = dstnb;
diama = newnod;
}
ht.pop_back();
}
ans[2*t] = dst;
ans[2*t + 1] = 1;
}
ans[1] = 1;
for(int i = 1; i<=n; i++){
cout<<ans[i]<<"\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14548 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
14452 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14548 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
14452 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14548 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
14452 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
