#618. 【JOISC2021】聚会 2
就是相当于选中的点在整棵树上的重心
首先，当\(i\)为奇数时，答案为\(1\)
当\(i\)为偶数时，可以将选中的点分为两个子树，分别记其根节点为\(x\)和\(y\)
那么可以发现，所以合法的\(x\)和\(y\)构成一个连通块，那么当前答案就是连通块的直径，且随着\(i\)的增大，连通块逐渐减小
那么点\(x\)在\(i=\min(n-sz[son[x]],sz[x])\)后退出连通块
这就意味着对于当前直径\((x,y)\)，\(y\)一定在\(x\)的\(sz\)最大的那棵子树里，\(x\)也一定在\(y\)的\(sz\)最大的那棵子树里
若\(y\)不在\(x\)的\(sz\)最大的那棵子树\(v\)中，那么设\(y\)在\(x\)的\(u\)儿子所代表的子树中，则因为\(y\)所代表的选中的点的个数为\(\frac i2\)，所以\(u\)的\(sz\)一定\(\geq \frac i2\)，那么\(sz_v\geq sz_u\geq \frac i2\)，那么\(x\)就可以向\(v\)的方向移动一个，这样可以保证\(v\)所代表的选中的点一定有\(\frac i2\)个
那么\(x\)久可以一直向后移动知道\(y\)在\(x\)的\(u\)儿子中且\(u\)是\(x\)的\(sz\)最大的那个儿子
#include<bits/stdc++.h>
#define pb push_back
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
const int N=2e5+5;
int n,q;
int head[N],cnt=1,sz[N];
struct node{
int nxt,v;
}tree[N<<1];
void add(int u,int v){
tree[++cnt]={head[u],v},head[u]=cnt;
tree[++cnt]={head[v],u},head[v]=cnt;
}
vector<int> pos[N];
int dfn[N],to[N<<1],tot,depth[N],st[N<<1][30];
void dfs(int u,int fa){
to[dfn[u]=++tot]=u,st[tot][0]=tot,depth[u]=depth[fa]+1,sz[u]=1;
int minn=n+5;
for(int i=head[u],v;i;i=tree[i].nxt){
if((v=tree[i].v)==fa) continue;
dfs(v,u),sz[u]+=sz[v],minn=min(minn,n-sz[v]),to[++tot]=u,st[tot][0]=dfn[u];
}
minn=min(minn,sz[u]),pos[minn].pb(u);
}
int lca(int u,int v){
u=dfn[u],v=dfn[v];
if(u>v) u^=v^=u^=v;
int k=log2(v-u+1);
return to[min(st[u][k],st[v-(1<<k)+1][k])];
}
int dis(int u,int v){
if(!u||!v) return -1;
return depth[u]+depth[v]-(depth[lca(u,v)]<<1);
}
struct use{
int u,v,len;
use(){}
use(int _u,int _v):u(_u),v(_v){ len=dis(u,v); }
}tr[N<<2];
use max(use a,use b){
return a.len>b.len?a:b;
}
void update(int rt){
tr[rt]=max(max(tr[lson],tr[rson]),max(max(use(tr[lson].u,tr[rson].v),use(tr[lson].u,tr[rson].u)),max(use(tr[lson].v,tr[rson].u),use(tr[lson].v,tr[rson].v))));
}
void Init(int l,int r,int rt){
if(l==r){
tr[rt]=use(l,r);
return;
}
int mid=l+r>>1;
Init(l,mid,lson),Init(mid+1,r,rson);
update(rt);
}
void modify(int l,int r,int rt,int p){
if(l==r){
tr[rt]=use(0,0);
return ;
}
int mid=l+r>>1;
if(p<=mid) modify(l,mid,lson,p);
else modify(mid+1,r,rson,p);
update(rt);
}
int main(){
scanf("%d",&n);
for(int i=1,u,v;i<n;++i) scanf("%d%d",&u,&v),add(u,v);
dfs(1,0),q=log2(tot);
for(int j=1;j<=q;++j) for(int i=1;i+(1<<j)-1<=tot;++i) st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
lca(2,4);
Init(1,n,1);
for(int i=1;i<=n;++i){
if(i&1) puts("1");
else{
printf("%d\n",max(1,tr[1].len+1));
for(auto u:pos[i>>1]) modify(1,n,1,u);
}
}
return 0;
}