| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1010201 | PoPularPlusPlus | Meetings 2 (JOI21_meetings2) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define vf first
#define vs second
const int mod = 1000000007;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 200004;
vector<int> adj[N];
int siz[N];
bool vis[N];
int ans[N];
int mx[N];
void cal_siz(int node , int par){
siz[node] = 1;
for(int i : adj[node]){
if(i!=par && !vis[i]){
cal_siz(i , node);
siz[node] += siz[i];
}
}
}
int centroid(int node , int par , int tot){
for(int i : adj[node]){
if(!vis[i] && i != par && siz[i] >= tot){
return centroid(i , node , tot);
}
}
return node;
}
void dfs(int node , int par , int dis){
mx[siz[node]] = max(mx[siz[node]] , dis);
for(int i : adj[node]){
if(i!=par && !vis[i])dfs(i , node , dis + 1);
}
}
void centroid_decomposition(int node){
cal_siz(node , node);
int tot = siz[node];
int root = centroid(node , node , (tot)/2);
cal_siz(root,root);
vector<pair<int,int>> v[tot + 2];
int mx_siz = 0;
for(int i : adj[root]){
if(!vis[i]){
mx_siz = max(mx_siz , siz[i]);
for(int j = 0; j <= siz[i]; j++){
mx[j] = -1;
}
dfs(i , root , 1);
for(int j = 1; j <= siz[i]; j++){
//cout << mx[j] << ' ';
v[j].pb(mp(mx[j],i));
sort(all(v[j]),greater<>());
while(v[j].size() > 2)v[j].pop_back();
}
//cout << '\n';
}
}
v[tot-mx_siz].pb(mp(0,-1));\
sort(all(v[tot-mx_siz] , greater<>()));
while(v[tot-mx_siz].size() > 2)v[tot-mx_siz].pop_back();
/*for(int i = tot; i >= 0; i--){
cout << i << '\n';
for(auto j : v[tot]){
cout << j.vf << ' ' << j.vs << '\n';
}
}*/
for(int i = tot; i >= 0; i--){
for(auto j : v[i + 1]){
v[i].pb(j);
}
sort(all(v[i]),greater<>());
if(v[i].size() >= 2){
if(v[i][0].vs == v[i][1].vs){
v[i].erase(v[i].begin() + 1);
}
}
if(v[i].size() >= 2){
if(v[i][0].vs == v[i][1].vs){
v[i].erase(v[i].begin()+1);
}
}
if(v[i].size() >= 2 && v[i][0].vs != v[i][1].vs){
ans[2*i] = max(ans[2*i] , v[i][0].vf + v[i][1].vf + 1);
}
}
vis[root] = 1;
for(int i : adj[root]){
if(!vis[i]){
centroid_decomposition(i);
}
}
}
void solve(){
int n;
cin >> n;
for(int i = 0; i < n - 1; i++){
int a , b;
cin >> a >> b;
adj[a].pb(b);
adj[b].pb(a);
}
memset(vis,0,sizeof vis);
memset(ans,-1,sizeof ans);
centroid_decomposition(1);
for(int i = n; i > 0; i--){
if(i % 2 == 1){;}
else {
ans[i] = max(ans[i] , ans[i + 2]);
}
}
for(int i = 1; i <= n; i++){
if(i % 2 == 1)cout << 1 << '\n';
else cout << ans[i] << '\n';
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//int t;
//cin >> t;
//while(t--)
solve();
}