This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define pb push_back
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define setmin(x,y) x=min((x),(y))
#define setmax(x,y) x=max((x),(y))
#define fi first
#define se second
// mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
// int rand(int l,int r){return l+((hdp()%(r-l+1))+r-l+1)%(r-l+1);}
const int N = 2e5+5;
const int mod = 998244353;
const int SQ = 450;
vector<int> g[N];
int n,k,ans[N],a1[N],a2[N],sz[N],mx;
bool b[N];
int dfs(int u,int p=0)
{
sz[u]=1;
for(auto v:g[u]) if(v!=p&&!b[v]) sz[u]+=dfs(v,u);
return sz[u];
}
int find(int u,int s,int p=0)
{
for(auto v:g[u]) if(!b[v]&&v!=p&&sz[v]*2>s) return find(v,s,u);
return u;
}
void add(int u,int p,int l=2)
{
setmax(a2[sz[u]],l);
for(auto v:g[u]) if(!b[v]&&v!=p) add(v,u,l+1);
}
void solve(int u)
{
u=find(u,dfs(u));
dfs(u);
for(int i=1;i<=sz[u];i++) a1[i]=1;
for(auto v:g[u]) if(!b[v])
{
add(v,u);
int cur=0;
for(int i=sz[v];i>=1;i--)
{
setmax(cur,a2[i]);
setmax(ans[2*i],cur+a1[i]-1);
}
cur=0;
for(int i=sz[v];i>=1;i--)
{
setmax(cur,a2[i]);
a2[i]=0;
setmax(a1[i],cur);
}
}
b[u]=1;
for(auto v:g[u]) if(!b[v]) solve(v);
}
signed main()
{
fastIO
cin>>n;
for(int i=1;i<=n;i++) ans[i]=1;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
g[u].pb(v);
g[v].pb(u);
}
solve(1);
for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |