首先考虑N^2做法,每次从一个点出发,如果到达一个点,然后到达这个点的时间(le)离这个点最近的叶子距离(di_x),那么答案+1,否则继续找点
这个暴力很不好优化.可以这样认为,如果某个点贡献答案,那么子树里的点也要贡献答案(某个点走不下去,那么走子树内的点也走不下去,也符合条件),不过一个子树一共只贡献1.可以发现一个子树度数和(sum deg_i),加上1为子树大小*2,即(sum 2-deg_i=1),所以单次询问的答案就是所有符合条件的点的(2-deg_i)之和
现在考虑每个点对(x,y),y对x的贡献,要满足(dis_{x,y}le di_y).考虑点分治,那么记某个点到分治重心距离为(dep_x),那么对x造成贡献的点y要满足(dep_x+dep_yle di_y),即(dep_xle di_y-dep_y),那么这个可以树状数组快速算贡献
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
#define il inline
#define re register
using namespace std;
const int N=7e4+10;
il int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int to[N<<1],nt[N<<1],hd[N],dg[N],tot=1;
il void add(int x,int y)
{
++tot,to[tot]=y,nt[tot]=hd[x],hd[x]=tot,++dg[x];
++tot,to[tot]=x,nt[tot]=hd[y],hd[y]=tot,++dg[y];
}
int n,fa[N],dd[N];
void dfs1(int x)
{
dd[x]=dg[x]==1?0:n+1;
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(y!=fa[x])
{
fa[y]=x,dfs1(y);
if(dd[x]>dd[y]+1) dd[x]=dd[y]+1;
}
}
}
void dfs2(int x)
{
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(y!=fa[x])
{
if(dd[y]>dd[x]+1) dd[y]=dd[x]+1;
dfs2(y);
}
}
}
int c[N<<1];
il void ad(int x,int y){while(x<=n+n) c[x]+=y,x+=x&(-x);}
il int gsm(int x){int an=0;while(x) an+=c[x],x-=x&(-x);return an;}
bool ban[N];
int sz[N],size,rt,rsz,st[N][2],tp,an[N];
void grt(int x,int ffa)
{
sz[x]=1;
int ma=0;
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(y!=ffa&&!ban[y])
{
grt(y,x),sz[x]+=sz[y];
ma=max(ma,sz[y]);
}
}
ma=max(ma,size-sz[x]);
if(ma<rsz) rsz=ma,rt=x;
}
void dfs3(int x,int ffa,int de)
{
st[++tp][0]=de,st[tp][1]=x;
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(y!=ffa&&!ban[y]) dfs3(y,x,de+1);
}
}
void cal(int x,int ffa,int op)
{
tp=0,dfs3(x,ffa,ffa>0);
for(int i=1;i<=tp;++i) ad(dd[st[i][1]]-st[i][0]+n,2-dg[st[i][1]]);
for(int i=1;i<=tp;++i) an[st[i][1]]+=op*gsm(st[i][0]+n);
for(int i=1;i<=tp;++i) ad(dd[st[i][1]]-st[i][0]+n,-(2-dg[st[i][1]]));
}
void sov(int x)
{
rt=0,rsz=size,grt(x,0);
x=rt;
cal(x,0,1),ban[x]=1;
for(int i=hd[x];i;i=nt[i])
if(!ban[to[i]])
{
int y=to[i];
cal(y,x,-1);
size=sz[y],sov(y);
}
}
int main()
{
n=rd();
for(int i=1;i<n;++i) add(rd(),rd());
dfs1(1),dfs2(1);
size=n,sov(1);
for(int i=1;i<=n;++i) printf("%d
",dd[i]?an[i]:1);
return 0;
}