/*题目意思是一开始我们只有1一个点之后2到m+1行会告诉我们一个变量这个变量是当前i的父节点,问每次加入一个点后有多少个树的直径端点,y总在树形dp的时候说过要找树的直径(边权一样的时候)那么就是先随便确定一个点,找离这个点最远的点再找离这个点最远的点这些点两两之间都是树的直径,在这里我们先假定选择的是根节点可以开两个set在存储两类,点一种是离根最远的点,第二类是离第一类点最远的点,这样两个集合里的数总和就是我们的答案了,对了之所以用set存储是为了去重复的点;
还有就是加入一个点我们要确定一下直径是否改变,如果新的直径和第一个集合到新的根距离一样则第一个集合不需要改动;
扫描第二个集合看看里面有没有第一类点有就加入第一个集合,第二类点清空把当前根放进去,反之也是一样的,如果等于那么把这个点放入对应集合就好其他点没有任何改动,如果小于那么更加是什么都不用动,然后计算直径的时候我们可以用最近公共祖先lca来实现
include [HTML_REMOVED]//这里的代码不想写注释了原谅孩子的懒吧,写到现在有点累了
include [HTML_REMOVED]
include [HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
set[HTML_REMOVED] s1,s2;
int f[300010][20];
int dep[300010];
int get(int a,int b)
{
int ans=0;
if(dep[a][HTML_REMOVED]=0;k–)
{
if(dep[f[a][k]]>=dep[b])
{
a=f[a][k];
ans+=(1<[HTML_REMOVED]=0;k–)
{
if(f[a][k]!=f[b][k])
{
ans+=(1<<(k+1));
a=f[a][k];
b=f[b][k];
}
}
return ans+2;
}
int main()
{
s1.insert(1);
dep[1]=1;
int m;
cin >> m;
int trm;
int mx=1;
for(int i=2;i<=m+1;i)
{
cin >> trm;
f[i][0]=trm;
dep[i]=dep[trm]+1;
for(int j=1;j<=19;j)
f[i][j]=f[f[i][j-1]][j-1];
int dist1=s1.empty()?0:get(i,(s1.begin()));
int dist2=s2.empty()?0:get(i,(s2.begin()));
if(max(dist1,dist2)>mx)
{
mx=max(dist1,dist2);
if(dist1==mx)
{
for(auto k:s2)
{
if(get(i,k)==mx)s1.insert(k);
}
s2.clear();
s2.insert(i);
}
else
{
for(auto k:s1)
{
if(get(i,k)==mx)s2.insert(k);
}
s1.clear();
s1.insert(i);
}
}
else if(max(dist1,dist2)==mx)
{
if(dist1==mx)s2.insert(i);
else s1.insert(i);
}
cout << s1.size()+s2.size()<<endl;
}
return 0;
}