Jzoj3555 树的直径

科学家在观测一棵大树，这棵树在不断地生长，科学家给这棵树的每个节点编了号。开始的时候，这棵树很小只有4个节点，一号点为根，其他三个节点挂在上面。

在接下来的M次观察中，科学家每次都能看见这棵树从叶子处长出新的两个节点来。如果当前这棵树有N个节点，那么这棵树的新的两个节点的编号分别为N+1，N+2。科学家记录下了这棵树生长的过程，需要你帮着计算这棵树实时的直径。树的直径就是这棵树最远的两个节点的距离。

每行一个整数x，代表这棵树的编号为x的节点下面又长了两个叶子节点。保证每次生长的节点都是叶子节点

好久没在jzoj上切题了，估计ranking都要掉了赶紧做一做今天的模拟题

还好第一题还比较简单，直接将新建节点和原来直径合并就好了，求lca就用倍增ok

#pragma GCC opitmize("O3")
#pragma G++ opitmize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int f[200010][18],d[200010],n;
inline void link(int p,int x){
	f[x][0]=p; d[x]=d[p]+1;
	for(int i=1;i<18;++i) f[x][i]=f[f[x][i-1]][i-1];
}
inline void swim(int& x,int d){
	for(int i=0;d;++i,d>>=1) if(d&1) x=f[x][i];
}
inline int gLca(int x,int y){
	if(d[x]>d[y]) swap(x,y);
	swim(y,d[y]-d[x]);
	if(x==y) return x;
	for(int j=17;;){
		for(;~j&&f[x][j]==f[y][j];--j);
		if(j<0) return f[x][0];
		x=f[x][j]; y=f[y][j];
	}
}
int main(){
	d[2]=d[3]=d[4]=1; *f[1]=0;
	f[2][0]=f[3][0]=f[4][0]=1;
	scanf("%d",&n); int x=2,y=3,r=2;
	for(int	p,c,t=4;n--;){
		scanf("%d",&c);
		link(c,++t); link(c,++t);
		p=gLca(x,t);
		if(d[x]+d[t]-2*d[p]>r){ r=d[x]+d[t]-2*d[p]; y=t; }
		p=gLca(y,t);
		if(d[y]+d[t]-2*d[p]>r){ r=d[y]+d[t]-2*d[p]; x=t; }
		printf("%d
",r);
	}
}