树的直径新求法
讲解题目
今天考了一道题目，下面的思路二是我在考场上原创，好像没人想到这种做法，，考场上的题目是这样的：
你现在有1 个节点，他的标号为1，每次加入一个节点，第i 次加入的节点标号为i+1，且每次加入的节点父亲为已经存在的节点。你需要在每次加入节点后输出当前树的直径。
大意：给你$n$个点，最开始时只有一个点，一号节点，然后每一次把第$i$号节点和编号比他小的节点相连，连接一个点后，求树的直径。
样例输入
第一行一个整数n。接下来n-1 行，第i+1 行一个数表示标号为i+1 的点的父亲。
612215
样例输出
一行n-1 个数，第i 个数表示加入i+1 号点后树的直径。
1 2 2 3 4
思路
先说一下常规的做法，我们看一下题目，会发现一个性质，很好的性质。在每一次加点之后，只有三种情况产生，第一种就是几点之后没有什么用，树的直径还是之前那个；第二种情况就是当前点和上一次的一个端点组成；而最后一种和第二种一样，只是是和另一个端点。用字母表示一下就是：设当前直径的表示方法为$(x1,x2)$，表示的是以$x1,x2$为两个端点的链。设新加进来的点为$y$，则新产生的树的直径只有三种情况：$(x1,y)$、$(y,x2)$、$(x1,x2)$。只需要维护一个倍增lca 和每个点的深度就行啦。这个不难想到（对与大佬们来说，像我这样的蒟蒻就没想到）。
虽然我没有想到，但是我自创了另一种做法。我们设$f[i]$表示的是以$i$号节点为根的子树中以$i$为端点的最长长度。这样我们计算答案时就很好计算了，我们只需要把新加进来的点旋转到整棵树的根，并更新$f$数组的值，把新加进来的点的$f$数组的值和上一个直径进行对比，去最大值就可以啦。难点就是旋转，大家还记的splay的旋转吗，这道题的旋转和splay的旋转的思路差不多，都是把儿子旋上去。但是相对而言这个更简单，因为我们不需要存他的儿子有谁，只需要存父亲就好了，但是我们发现旋转的时候旋下来的点的$f$数组的值会改变，所以我们需要重新更新。怎么更新呢？我们每一次都在和当前旋下来的点有一条边相连的所有点中选取$f$值最大的，并加一赋值，但有一个细节，就是这些点中不能包括要选上去的点。每一次更新就好啦。
时间分析
可能有人会问，这个不是$O(N^2)$的时间复杂度吗？虽然是期望$log_2^n$层，但是数据卡一卡就能卡成链，退化成$N^2$的算法啦。但是不要忘记，我们是有旋转操作的，旋来旋去，就成了一棵类似于平衡树的东西，因为你也不知道怎么旋，在没看代码的情况下，所以数据你做不出来，哈哈。再想一想，splay的精妙之处不也是这里吗？因为旋转成了平衡树。结束，时间复杂的$O(n*log_2^n)$。是不是很好？
代码
#include#include using namespace std;#define N 200001int head[N],to[N*2],nxt[N*2];int ans,idx,n;int f[N];int lenth[N];void add(int a,int b){nxt[++idx]=head[a],head[a]=idx,to[idx]=b;}void change(int p,int from){ if(f[p]) change(f[p],p); lenth[p]=0; for(int i=head[p];i;i=nxt[i]) if(to[i]!=from) lenth[p]=max(lenth[p],lenth[to[i]]+1); f[p]=from;}int main(){ scanf("%d",&n); for(int i=2;i<=n;i++) { scanf("%d",&f[i]),add(f[i],i),add(i,f[i]); change(f[i],i),lenth[i]=lenth[f[i]]+1,f[i]=0; ans=max(ans,lenth[i]); printf("%d ",ans); }}
有不懂得，可以发评论提问，这种做法纯属原创。