观察：当 $N>2$ 时，一个合法的排列恰好属于以下两者之一：

• A：$P_1=2$，且删除 $P_1$ 并将大于 $2$ 的数减 $1$ 后是合法的排列。
• B：$P_2=1$，且删除 $P_2$ 并将所有数减 $1$ 后是合法的排列。

因此恰好有 $2^{N-2}$ 种合法的排列，可以从 $[2,1]$ 开始每次进行上述 A、B 之一的逆操作共 $N-2$ 次得到。

我们把这个操作序列记作 $S$，则容易发现树的直径等于 $S$ 的连续段数 $+1$。

而 LIS 可以这样求出：设 $x,y$ 分别表示以 $P_1$ 和 $1$ 作为开头的 LIS 长度，则初始时 $x=y=1$，操作 A 会使得 $x=\max\{x+1,y\}$，操作 B 会使得 $y=\max\{y+1,x\}$。这个答案还可以用另一种方式求出：初始答案为 $1$，从 $S$ 的末尾开始，假设 $S$ 的末尾为 A，一直往前找，删除所有单独的 B，直到遇到连续的两个 B 或者 $S$ 的开头；如果在这之前遇到了 $k$ 个 A，则将答案增加 $k-1$，然后从连续的两个 B 开始继续往前重复这样的操作直到开头。这个算法的正确性可以考虑每一次操作之后 $x$ 和 $y$ 的大小关系。

上述的操作实际上把 $S$ 分成了若干段，如果我们把 $S$ 的最后一个字符复制一遍，则每一段形如 (AB?)*AA，最后开头可能有一个孤立的字符。例如 $\tt {\color{red}A}BABB{\color{red}AABABAA}$ 对应排列的 LIS 是 $1+(5-1)+(3-1)=7$。

我们用 $x$ 表示长度，$y$ 表示直径，$z$ 表示 LIS，则上述一段的生成函数是： $$ \frac{x^2yz}{1-(xz+x^2y^2z)} $$ 设 $f_{i,j,k}$ 表示长度为 $i$（也就是排列大小等于 $i+1$），直径为 $j$，LIS 为 $k$ 的操作序列数量，则其生成函数为： $$ \sum_{i,j,k} f_{i,j,k}=\frac{2(1+xy)yz}{1-\frac{x^2yz}{1-(xz+x^2y^2z)}}=\frac{2(1+xy)(1-xz-x^2y^2z)yz}{1-xz-x^2y^2z-x^2yz} $$ 注意上述生成函数在 $N=2$ 时不对，需要特判。

我们要计算的是关于 $y$ 的多项式 $$ \sum_{j,k} f_{N-1,j,k}y^jk^K $$ 我们对于生成函数分子的每一项分别求其贡献，主要难点是怎么处理分母。注意到分母可以写成 $1-xz-x^2z(y+y^2)$，我们令 $t=y+y^2$，则分母等于 $1-xz-x^2zt$，这相当于由 $xz$ 和 $x^2zt$ 构成的序列，我们枚举每一项出现了几次就能计算贡献。具体的，假设分子上是 $cx^iy^jz^k$，则这一项的贡献就是 $$ cy^j \sum_l l^K[x^{N-1-i}z^l] \frac{1}{1-xz-x^2zt}=cy^j\sum_{l}{N-1-i-l\choose l} t^l (N-1-i-l+k)^K $$ 最后的求和是一个关于 $t$ 的多项式，我们还需要带入 $t=y+y^2$。也就是将一个多项式 $f(x)$ 复合 $x+x^2$，因为 $x+x^2=\left(x+\frac{1}{2}\right)-\frac{1}{4}$，我们只需要依次复合 $x-\frac{1}{4},x^2,x+\frac{1}{2}$ 即可。复合 $x+k$ 需要一次卷积。

最终我们需要执行 $6$ 次这样的复合，总复杂度 $O(N\log N)$。但是这个算法的常数非常大，需要比较快的卷积板子还有常数优化。最显著的一个优化是利用 $y^2=t-y$ 将分子中的 $y$ 消成只有 $0$ 次和 $1$ 次项，然后将 $y$ 的次数相同的一起处理，这样就只需要 $2$ 次复合。