A

把所有形如$(a,ka)$的路径提出来，共有$O(n\log n)$条路径，后面将这种路径称为限制。

考虑答案路径如果要不合法，那么必然覆盖了至少一条完整的限制。

考虑覆盖限制$(u,v)$的路径$(a,b)$，设$dfn_x$表示$x$的$dfs$序，$end_x$表示$x$的子树中最大的$dfs$序，不妨设$dfn_u < dfn_v,dfn_a < dfn_b$。

1. 当$u$是$v$的祖先的时候，考虑$g$是离$u$最近的路径$(u,v)$上的点，要么$dfn_a < dfn_g,dfn_v\leq dfn_b\leq end_v$，要么$dfn_v\leq dfn_a\leq end_v,dfn_b>end_g$。
2. 当$u$不是$v$的祖先的时候，显然$dfn_u\leq dfn_a\leq end_u, dfn_v\leq dfn_b\leq end_v$。

第一种情况构成了$2$个矩形，第二种情况构成了$1$个矩形。

最终我们只要求出所有矩形的并然后取个反即可，扫描线$+$线段树，总复杂度$O(n\log^2 n)$。

B

观察一下可以发现，如果将同一行与同一列的$1$用边连起来，一种方案可以拆成很多个环，从这个方面入手。

设$f_n$表示$n\times n$矩阵的答案，我们枚举第一行所在环的大小，那么有递推式： $$f_n = \sum_{i = 2}^{n}A_i\cdot \binom{n}{i}\cdot \binom{n - 1}{i - 1}\cdot f_{n - i}$$

其中$A_i$表示$i\times i$的矩阵只有一个环的方案数，$\binom{n}{i}$表示选出$i$列，$\binom{n-1}{i-1}$表示选出除了第$1$行的剩下的$i-1$行。

先给出结论：$A_n = \frac{n!(n-1)!}{2}$，那么式子化成： $$f_n = \sum_{i = 2}^{n}\frac{i!(i-1)!}{2}\cdot \binom{n}{i}\cdot \binom{n - 1}{i - 1}\cdot f_{n - i}$$

将组合数拆开化简，得到： $$f_n = \frac{n!(n-1)!}{2}\sum_{i = 2}^{n}\frac{f_{n-i}}{((n-i)!)^2}$$

设$g_n = \frac{f_n}{(n!)^2}$，那么有： $$g_n = \frac{1}{2n}\sum_{i = 2}^{n}g_{n - i}$$

维护前缀和即可，复杂度$O(n)$。

现在考虑怎么证明$A_n = \frac{n!(n-1)!}{2}$。

先$n!$每行每列放一个$1$，设$p_i$表示第$i$行$1$的列编号。在$p_1$列放第二个$1$ 有$n-1$种方案，假设第二个$1$行号为$q_i$，那么接下来考虑$p_{q_i}$列，这列第二个$1$有$n-2$ 种放法，因为不能在此时返回第一行，再加上已有$2$个$1$的行不能再放$1$。接下来就是$n-3...$。除以二是因为这个过程的逆过程也被计算过了。

C

一眼费用流裸题，但是数据范围有点大，考虑动态维护流量。

设当前加入的点编号为$x$，因为深度是$O(\log n)$的，因此我们可以枚举$x$和$x$要到的点的LCA，对于当前LCA设为$g$，我们需要求出$g$往子树中走最小的代价使得可以流到一个还有剩余容量的点，设为$down_g$。注意子树中行走的代价可以根据每条边的流量正负来确定，因此要维护每条边的流量，其实就是手动维护网路流。我们需要求出$down_g+cost(x\rightarrow g)$中代价最小的那个，然后暴力维护每条边的流量即可。

复杂度$O(n\log n)$。