[破碎的状态] [-11] 690 C3
题意:
给你个节点
每次向里面加一个点以及这个点连一条边到一个已知点
每次操作后求树的直径(即两点的距离的最大值)
这一题
我们考虑一个离根最远的点
它dfs一遍得到的所有点的最远点就是答案
所以我们维护这个最远点
如果某个点更远,那么就把它改为最远点,同时我们认定,直径+1
(这里直径+1可以理解为,本身某个点更远,那么它的父亲肯定在一条最长链上,那么
否则,求它和最远点的距离
这可以写个LCA
#include<set> #include<map> #include<list> #include<queue> #include<stack> #include<string> #include<time.h> #include<math.h> #include<memory> #include<vector> #include<bitset> #include<fstream> #include<stdio.h> #include<utility> #include<sstream> #include<string.h> #include<iostream> #include<stdlib.h> #include<algorithm> using namespace std; int depth[200005]; int up[200005][25]; int father[200005]; int lca(int x,int y) { if (depth[x]<depth[y]) swap(x,y); int t=depth[x]-depth[y]; int i; for (i=0;i<20;i++) { if ((1<<i)&t) x=up[x][i]; } for (i=19;i>=0;i--) { if (up[x][i]==up[y][i]) continue; x=up[x][i]; y=up[y][i]; } return father[x]; } int main() { #ifdef absi2011 freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif int n; scanf("%d",&n); int i; int farest_point=0; int farest_depth=0; int ans=0; for (i=0;i<20;i++) { up[0][i]=-1; } for (i=1;i<n;i++) { int x; scanf("%d",&x); x--; father[i]=x; depth[i]=depth[x]+1; int j; up[i][0]=x; for (j=1;j<20;j++) { if (up[i][j-1]==-1) { up[i][j]=-1; } else { up[i][j]=up[up[i][j-1]][j-1]; } } if (depth[i]>farest_depth) { farest_point=i; ans++; farest_depth++; printf("%d ",ans); continue; } int t=lca(i,farest_point); if (depth[i]-depth[t]+farest_depth-depth[t]>ans) { ans++; } printf("%d ",ans); } return 0; }