codeforces 442D Adam and Tree

题意:

给出一棵树，最开始只有1个节点。

每个时刻，这棵树会长出一个叶子。

树上每条边都有且只有1种颜色，并且同一种颜色的边都连通。

定义一个点到根的距离为该点到根的路径上的颜色种数。

求每个时刻树上最大距离的最小值。

分析:

考虑每次向上更新dp值，直到更新到根或者不能更新为止。

由树链剖分可知这样做的复杂度是O(nlogn)的。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAXN=1e6+5;

int n;

int dp[MAXN],p[MAXN];

int mx1[MAXN],mx2[MAXN];

int main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout); 
	scanf("%d",&n);
	puts("0");
	for(int i=2;i<=n;++i){
		scanf("%d",p+i);
		dp[i]=1;
		int cur=i;
		while(cur!=1){
			int par=p[cur];
			if(dp[cur]>mx1[par]){
				mx2[par]=mx1[par];
				mx1[par]=dp[cur];
			}
			else if(dp[cur]>mx2[par]){
				mx2[par]=dp[cur];
			}
			cur=par;
			int res=max(mx1[cur],mx2[cur]+1);
			if(res==dp[cur])break;
			dp[cur]=res;
		}
		printf("%d\n",mx1[1]);
	}
	return 0;
}