基环树的一些基本问题

其实没啥。

主要就两个

一、求基环树的最大直径
二、判环的简洁办法

其中第一个问题比较关键，是一个非常常用的基环树森林模型。而且我基环树虽然写了7，8道了，写的却总是很冗长。基本全靠码力弥补才勉强不出错。。最近写的题目也是调了很久不出来，就是代码不够简洁导致的。很多细节可以处理的非常的简洁但是我却选择了复杂的思路。

一：

先说关键的模型吧。其实就是一个单调队列的事情。但是我之前没有想到这个，导致我赛时没做出来。后面只是弄懂了但是没有专门来补，所以也没有系统的整理这方面的东西。现在来整理了，也是因为刚刚好发现这个模型吧。大致就是先把链拆开，然后维护单调队列，我们把价值函数写出来\(val=s[i]+s[j]+d[j]-d[i]\)，其中\(s[i]\)表示以第i个点为根的子树的深度，\(d[i]\)表示第\(i\)个点在链上的位置，其中\(j>i\)。我们可以发现，维护这个东西的最大值，其实就是对于\(j\)维护最大的\(s[i]-d[i]\)，当一个位置的\(i_2\)满足\(s[i_2]-d[i_2]>s[i_1]-d[i_1]\)，且\(i_2>i_1\)，那么\(i_2\)就一定比\(i_1\)更优秀，在任何情况下都不可能会选择\(i_1\)。

我刚刚学的那段时间可能能够一眼看出来吧，因为确实是一个非常明显的单调性，随着长度的增加，之前不优秀的不会变的优秀。这个已经够明显了。

除此之外，还有树的直径的计算，可以直接用dp求最长路，我每次还写个次长。。导致要花掉挺多精力的。

二：

这个没有上一个问题关键，放个伪代码就懂了吧

int dfs_huan(int x)
{
    vis[x]=1;
    return (vis[u[x]]==1)?x:dfs_huan(u[x]);
}

当时看到了还楞了一下，真心挺简洁。

就这样吧，这些都是非常基础的。。我都不知道为什么要写这个，就像不知道为什么我没想到单调队列一样。