树的直径新求法

讲解题目

　　今天考了一道题目，下面的思路二是我在考场上原创，好像没人想到这种做法，最原始的题目，考场上的题目是这样的：

　　你现在有1 个节点，他的标号为1，每次加入一个节点，第i 次加入的节点标号为i+1，且每次加入的节点父亲为已经存在的节点。你需要在每次加入节点后输出当前树的直径。

　　大意：给你$n$个点，最开始时只有一个点，一号节点，然后每一次把第$i$号节点和编号比他小的节点相连，连接一个点后，求树的直径。

样例输入

　　第一行一个整数n。接下来n-1 行，第i+1 行一个数表示标号为i+1 的点的父亲。

样例输出

　　一行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 <stdio.h>

#include <algorithm>

using namespace std;

#define N 200001

int 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);

	}

}

　　有不懂得，可以发评论提问，这种做法纯属原创。

巴特西

树的直径新求法、codeforces 690C3 Brain Network (hard)

树的直径新求法

讲解题目

样例输入

样例输出

思路

时间分析

代码

最新文章

热门文章