DTOJ 4771. Barbecue

题意

Lyra 去野外旅游，准备试验刚买的烧烤架，于是她走到了附近的一棵树下想把树的一部分砍下来作为燃料。

树可以看成一棵 $n$ 个点编号为 $1\cdots n$ 的有向无环图， Lyra 要求她砍下来的部分必须是一个连通块，编号也必须连续，她想知道她有多少种不同的砍法。

即给定一棵树，问多少个不同的区间 $[L,R]$ 满足编号为 $[L,R]$ 的点在树上组成一个连通块。

对于 20% 的数据， $n\le 300$；

对于 40% 的数据， $n\le 2000$；

对于额外 20% 的数据，输入构成一条链；

对于 100% 的数据， $T\le 15,1\le u,v\le n\le 3\times 10^5,\sum n\le 2\times 10^6$

题解

一条链可以考虑在链上分治，每次需要计算$[l,r]$内跨过$mid$的合法区间个数，合法区间$[l,r]$等价于$mx-mn=r-l$，于是枚举$r$，用指针维护一下所有$l$应该贡献在哪里，用数组记一下即可（这比正解难写多了。。。）

对于树上，不知道为什么原本会往点分治想，但联通块的问题效率是无法保证的！！！

于是只能考虑对于编号分治了，但一段编号区间联通怎么转化呢？
注意到树的结构的特殊性，即两个点之间有且仅有一条简单路径，所以这段区间的任意两个点之间的所有点都应出现在区间中。
这样还是不好算，又注意到只需要一一个点为媒介，其它所有点到这个点的路径上的点都出现在区间中即可。
于是以$mid$为根，区间内所有点到$mid$的路径上的点都要在区间内，记每个点到$mid$路径上的点的最大最小值$mn,mx$，即$[l,r]$内$mn$的最小值$=l$，$mx$的最大值$=r$，于是枚举$r$，对于合法的$r$，维护$l$的合法区间，计算区间内有多少个合法的$l$即可。