codeforces 442D Adam and Tree
题意:
给出一棵树，最开始只有1个节点。
每个时刻，这棵树会长出一个叶子。
树上每条边都有且只有1种颜色，并且同一种颜色的边都连通。
定义一个点到根的距离为该点到根的路径上的颜色种数。
求每个时刻树上最大距离的最小值。
分析:
考虑每次向上更新dp值，直到更新到根或者不能更新为止。
由树链剖分可知这样做的复杂度是O(nlogn)的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | #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;} |
评论 (0)
