#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 2e5+5;
vector<int> g[maxn];
int sz[maxn], L[maxn], R[maxn], par[maxn], dep[maxn];
vector<int> children[maxn]; // including self
int IT = 0;
int lca[4005][4005];
void dfs1(int v, int p) {
par[v] = p;
sz[v] = 1;
L[v] = R[v] = IT++;
children[v].pb(v);
for (int u : g[v]) {
if (u != p) {
dep[u] = dep[v] + 1;
dfs1(u,v);
sz[v] += sz[u];
R[v] = R[u];
for (int c : children[u]) {
children[v].pb(c);
}
}
}
}
bool isAnc(int a, int b) {
// is a b's ancestor?
return L[a] <= L[b] && R[a] >= R[b];
}
int n;
vector<int> quadratic() {
dfs1(0, -1);
REP(i,n) {
for (int c : children[i]) {
lca[i][c] = lca[c][i] = i;
}
for (int c : g[i]) {
if (c != par[i]) {
for (int c2 : g[i]) {
if (c2 > c && c2 != par[i]) {
for (int v1 : children[c]) for (int v2 : children[c2]) {
lca[v1][v2] = lca[v2][v1] = i;
}
}
}
}
}
}
vector<int> dst(n); // max accommodation for this length
REP(i,n) REP(j,i) {
int a = i, b = j;
if (dep[a] > dep[b]) swap(a,b);
int s1, s2;
if (isAnc(a,b)) {
s1 = n-sz[a]+1;
s2 = sz[b];
}else{
s1 = sz[a];
s2 = sz[b];
}
bug(a,b,lca[a][b], s1, s2);
bug(dep[a] + dep[b] - dep[lca[a][b]] * 2);
MX(dst[dep[a] + dep[b] - dep[lca[a][b]]*2], min(s1, s2) * 2);
}
for (int i = n-2; i>=0; --i) {
MX(dst[i], dst[i+1]);
}
vector<int> ret(n+1);
int j = 1;
for (int i = n; i>=1; --i) {
if (i % 2 == 1) ret[i] = 1;
else{
while (j+1 < n && dst[j+1] >= i) {
++j;
}
ret[i] = j+1;
bug(i, ret[i]);
}
}
return ret;
}
signed main(){
IOS();
cin>>n;
REP(i,n-1) {
int a,b; cin>>a>>b; --a; --b;
g[a].pb(b); g[b].pb(a);
}
vector<int> yay = quadratic();
REP1(i,n) {
cout<<yay[i]<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9748 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
9760 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9748 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
9760 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9748 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
9760 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
