君よ いっそいっそ いなくなれ

変わらない このままなら

显然题中生成的BST就是笛卡尔树，但是如果因此就往子树合并类的DP想的话就寄了（比如我）。

正确的做法是，将点的深度转化为祖先的个数，进而转化为每个点成为它祖先的方案数。即

$$Ans_u=\sum_v{\sum_{BST} [v\in anc(u) ]}$$

而 $ [v\in anc(u) ]$ 的充要条件是 $v$ 是 $u,v$ 间的最小值。

如果不考虑 $(u,v)$ 的限制，计算恰有 $k$ 个逆序对的排列数是经典的。令 $f_{i,j}$ 表示 $i$ 个数的排列，已有 $j$ 个逆序对的方案数，枚举 $p_i$ 与前 $i-1$ 位的相对大小，有

$$f_{i,j}=\sum_{k=0}^{i-1} f_{i-1,j-k}$$

这是可以写作生成函数的，令 $F_i=\sum f_{i,j}x^j$，有

$$F_n=\frac{\prod_{i=1}^n(1-x^i)}{(1-x)^n}$$

这允许我们 $O(n^3)$ 的计算总方案数。

现在有了 $(u,v)$ 的限制，先考虑 $u>v$ 的情况。

注意到上面的DP实际上是在往排列中一个一个塞数，而往最前端塞和最后端塞实际上是等价的。

那我们可以先将 $u,v$ 间的数先塞完，那么其它数就跟正常一样的。而增加的限制无非就是在塞 $v$ 的时候令 $k=0$，因为 $v$ 最小，无法产生逆序对。记 $L=u-v+1$，那么我们只用撤销第 $L$ 次转移，即

$$G=\frac{\prod_{i=1}^n(1-x^i)}{(1-x)^n} \frac{1-x}{1-x^L}$$

那么当前的贡献就是 $[x^k]G$。

上面的式子直接算的话是 $O(n^4)$ 的。

我们可以先预处理 $\prod_{i=1}^n(1-x^i)$，并递推求出 $(1-x)^{n-1}G$，然后计算 $[x^k]G$，就可以做到 $O(n^3)$了。

对于 $u<v$ 的情况，无非就是在塞 $v$ 的时候令 $k=L-1$，做法是类似的，不再赘述。

注意到还有 $u=v$ 的贡献，其实就是没有限制的方案数。

于是总时间复杂度 $O(n^3)$。

我等必将复起,古木已发新枝。

前置是Pro3575。

首先把二分图判掉。

回顾一下我们的连边方式可以发现，图中的边只有三类：

1. $(x-1,y-1) \to (x,y)$.

2. $(x-1,y+1) \to (x,y)$.

3. $(x,x+1) \to (x,x+1)$.

显然，每层的方案数互不影响，于是我们可以逐层计算，最后乘在一起即可。

根据有关链头的分析，我们不难得到一个DP：

令 $f_{i,j}$ 表示考虑前 $i$ 个点，且第 $i$ 个点向右留了 $j$ 个链头的方案数。

考虑从 $f_{i-1,k}$ 转移到 $f_{i,j}$。那么 $i$ 中的 $j$ 个点继承前面的链头，剩下 $cnt_i-j$ 个点去连 $fa_i$，那么有

$$f_{i,j} \gets f_{i-1,k} C_{cnt_i}^{j} (2^{cnt_{fa_i}}-1)^{cnt_i-j} g(cnt_{i-1},k,cnt_i,j)$$

其中 $g(n,x,m,y)$ 表示在数量分别为 $n,m$ 的两组点之间连边，使得第一组的前 $x$ 个点以及第二组的前 $y$ 个点都有连边的方案数。

枚举 $x$ 个点中不合法的个数进行容斥，得到

$$g(n,x,m,y)=\sum_{i=0}^{x}(-1)^i C_{x}^{i} (2^{n-i}-1)^y\ 2^{(n-i)(m-y)}$$

转移是有条件的。当 $i$ 为层左端时，$j=0$。当 $fa_i$ 不存在时，$j=cnt_i$。

最后是统计答案。

若本层的右端不是 $(x,x+1)$，那么贡献就是 $f_{i,0}$。

否则，$f_{i,j}$ 需要乘上其内部连边的方案数。不难发现就是在 $cnt_i$ 个点间任意连边(可以自环)，使得前 $j$ 个点都有连边的方案数，记作 $h(cnt_i,j)$。

类似的容斥，得到

$$h(n,x)=\sum_{i=0}^x (-1)^i C_{x}^{i} 2^{\frac{(n-i)(n-i+1)}{2}}$$

最终对答案的贡献就是 $\sum f_{i,j}h(cnt_i,j)$。

然后是节点 1 的保留节目。注意到如果节点 1 有自环，那么这个自环在新图中也是必须有的，而我们会当做有无均可计算，所以答案需要 $/2$。

恰当的预处理可以做到时间复杂度 $O(n^3)$。

实际上还有 $O(n^2)$ 的原神做法，但是我不会。一定是原神等级太低导致的。

只要不失去你的崇高,整个世界都将为你敞开。

喜报：本人在写完本文后，由于网站自动注销，且文章没有保存，成功丢失了全稿。现在这篇是本人又码了一遍得到了。令人忍俊不禁。

注意到 $f$ 只与原图的奇/偶最短路有关，那么每个点在两个图上的奇/偶最短路应该都是相同的。

若原图是二分图，那么答案为任意一棵生成树。

否则，所有点的奇/偶最短路均存在，记作 $(x,y)$。又发现两者的顺序无影响，于是不妨令 $x \lt y$。

考虑一个点 $(x,y)$ 的连边方式：

1. $(x-1,y-1) \to (x,y)$.

2. $(x-1,y+1) \to (x,y) \gets (x+1,y-1)$.

3. $(x-1,x+2) \to (x,x+1) \gets (x,x+1)$.

实际上③是②在 $y=x+1$ 时的特殊情况，但是很有用。

注意到②③中 $x+y$ 是不变的，这启示我们将点按照 $x+y$ 分层。而①中又有 $y-x$ 不变，这启示我们在每层中按照 $y-x$ 升序。

此时我们的连边方式就变得直观了。考虑在以 $x+y$ 为横轴，$y-x$ 为纵轴的坐标系中，我们的连边方式体现为：

1. 向正下方的点连边（如果存在）。

2. 向左右的点分别连边 （如果存在）。

3. 每层最右侧的点，若是 $(x,x+1)$，那么它可以和自己连边。

可以画个图理解一下。

显然①是最划算的，但问题是 $(x-1,y-1)$ 可能不存在，此时我们必须使用②③。

分析一下②③，可以发现本质是将一条链不断往右延伸，并最终在 $(x,x+1)$ 内部消化。显然我们应该将链两两配对，来省去一般代价。

现在我们来分讨一下策略。

考虑点 $(x,y)$，记它包含 $cnt$ 个节点，令 $(x-1,y-1)=fa,(x-1,y+1)=lst$，那么：

1. 若 $fa$ 存在， $lst$ 不存在。那么就直接全连①即可，不向后面留任何链头。

2. 若 $fa$ 不存在， $lst$ 存在。那么就只能全连②，并向后留 $cnt$ 个链头。

3. 若 $fa$ 与 $lst$ 均存在。分析一下可以发现，我们应该让前面的链头尽量分散地连到当前点，再向右传递下去。如果还有剩的，就用①连。

4. 若 $fa$ 与 $lst$ 均不存在。显然这是不可能出现的，因为原图的存在实际上已经为有解做了保障。

可以发现，只有②会产生链头。

最后我们会到达本层的最右端。

若它为 $(x,x+1)$。记它后面还有 $c$ 个链头，通过两两配对，只需要 $\left \lceil \frac{c}{2} \right \rceil $ 的代价。

否则，因为有解，本层一定不存在任何链头。

其实还没完，由于节点 1 并不需要连边，需要特殊处理。要留意一下节点 1 有自环的情况。

可以用 map 之类的实现，时间复杂度 $O(n\log n)$。

Link. 有附加内容。懒得搬了。

最喜欢的一集。

题目的要求十分简洁，但是贡献的计算非常繁琐诡异，而 $n$ 非常小。基本上可以直接放弃别的想法直奔网络流了。

观察一下贡献的形式，发现 $d_{i, j}$ 的贡献方式是我们熟悉的，可以用最大权闭合子图的模型来描述。所以考虑一下最小割。

除了 $d_{i, j}$ 我们还有一个 $mx^2 + cx$ 的贡献。这两个贡献仍然可以看作最大权闭合子图。具体地，选上 $d_{i, i}$ 后会产生 $ma_i^2$  的代价，如果之前已经产生过了则无所谓。给每种类型建一个点即可。

类似地，$cx$ 可以平摊到每次选 $x$ 的位置上，对 $d_{i, i}$ 对应的 $a_i$ 建立点 $A_i$ 并连边，表示选上 $d_{i, i}$ 则必须选上 $-a_i$。

然后就没了。讲一下最大权闭合子图，考虑这样一个模型：给定一张 $n$ 个点 $m$ 条边的有向图。每个点有代价 $a_i$，可正可负。你可以选上一些点，你的分数是你选的点的 $a$ 之和。但是选点有限制，选上一个点 $x$ 则必须选上 $x$ 能到达的所有点。求最大分数。

这个过程可以看作，选一些正权点，为了得到它们的权值不得不割舍一些负权点的代价。

于是考虑转化一下限制，改写成：选一些正权点，选上一个点后必须选上其所能到达的负权点。

这样做的好处在于，即简化了问题，又保证答案不会改变。感觉非常妙。

然后就是最小割建模。建立源汇点 $S, T$，对于每个正权点 $i$，连 $S\to i$，流量为 $a_i$。对于每个负权点 $i$，连 $i\to T$，流量 $-a_i$。对于正权点 $i$ 和其所能到达的负权点 $j$，连边 $i\to j$，流量 $+\infty$。答案即为正权点权值和减去最小割。

首先建立超源点和超汇点，源点与类型相连，试题与汇点相连，类型与对应试题相连

之后考虑边的容量

每种类型需要的试题有多道，所以源点与类型的边的容量应为该类型所需试题的数量

一道题只有一个，所以试题与汇点的边的容量为1，同理类型与试题的边的容量也为1

求最大流后进行判断，如果最大流等于m，那么寻找容量为0的边对应的类型和试题输出，否则无解

将每天拆成两个点，i点用于接收干净餐巾，i'点用于接收脏餐巾，那么：

·从i向T连流量为Ri，费用为0的边，如果满流则表示当天的餐巾数量足够

·从S向i'连流量为Ri，费用为0的边，表示每天结束时接收到Ri块脏餐巾

·从S向i连流量为∞，费用为p的边，表示每天开始时购买餐巾

·从i'向i+m连流量为∞，费用为f的边，表示送快洗

·从i'向i+n连流量为∞，费用为s的边，表示送慢洗

·从i'向(i+1)'连流量为∞，费用为0的边，表示将脏餐巾留到下一天

之后求最小费用最大流即可