A

注意到在矩形内的线段也是一条线段。求出线段的两个端点。

特判掉无解，求线段和矩形四条边的两个交点（注意端点在矩形内部）

时间复杂度为 $O(1)$。

B

DAG 上支配树。考虑能支配点 $x$ 的点集和点 $x$ 在支配树上的祖先集合等价。

具体的，插入第 $i$ 个点前，得到 $1\sim i-1$ 个点的支配树。

如果这个点受点集 $S$ 支配，则找到深度最大的点支配点集 $S$，体现在支配树上就是公共 LCA。

找到这个点后插入，因为要动态加叶子求 LCA，所以需要倍增。

按照拓扑排序加入叶子，查询时处理公共最近祖先。时间复杂度为 $O((n+m+q)\log n)$。

C

可以先按照大小排序。

然后求差分数组的 $\gcd$，正确性显然。

时间复杂度为 $O(n\log n)$。

D

$u_i=a_i-\min(a_i,b_i),v_i=b_i-\min(a_i,b_i)$。

注意到 $u_i,v_i$ 至少一个为 $0$。然后对有值的 $v_i$ 的取前 $k$ 大。

感觉不是很对，可以全取 $b_i$，然后取 $b_i-c_i$ 最小的几个。

时间复杂度为 $O(n\log n)$。

E

求出图的任意生成树，$(x,y)$ 的路径为从 $x\to y$ 的树上路径异或权值异或上任意一个环的异或权值。

实际上只需要把经过 $1$ 的环塞进去线性基就能表示所有环，时间复杂度为 $O(n\log V)$。

F

省流 $n^2m^2\le q$。

直接预处理出任意位置的答案，时间复杂度为 $O(n^2m^2+q)$。

G

$\min(a_i,b_i,c_i)$。

H

强强。

显然只需要满足任意 $i+1$ 大小的集合大于任意 $i$ 大小的集合。

显然只需要满足任意前 $i+1$ 大小的集合大于后 $i$ 大小的集合。

感觉一下，$i$ 越大越难满足，只需要让 $i=\left\lfloor\frac{n}{2}\right\rfloor$ 即可。

如何刻画单调递增，只需要令所有 $A_i=m$，每次减去一个前缀。记 $c_i$ 为 $1\sim i$ 减了 $c_i$ 次。

然后不会了，爽贺题解。

记 $d$ 表示前 $k+1$ 个减去后 $k$ 个的值，只需要满足条件 $d>0$。

可以求出 $c_i\gets c_i+1$ 会导致答案的变化 $w_i$。

要使得设 $dp_{i,j}$ 表示让 $c_k$ 变了 $i$ 次，$d=j$ 的方案数。

直接 $O(nm)$ 背包 dp 即可。

I

初见杀。

注意到前缀和和 $a_i$ 是双射，对前缀和处理。

已知 $s_0=0$，已知花费 $w_{l,r}$ 的代价可以知道 $s_{l-1},s_r$ 之间关系。

转化为最小生成树模型，Prim 可以 $O(n^2)$。

J

怎么感觉可以手算预处理出来当前面经过某种操作后是那个面（。

然后自动机（，时间复杂度为 $O(q)$。

K

差分，随便做。

L

显然分数规划。

每次一定减去 $[2,n-1]$ 中的最大子段和。

时间复杂度为 $O(n\log V)$。

Sol 1

我们从左往右扫描离散化出来的线段 $i$（设当前点权为 $v_i$）。维护一个集合 $S$，表示覆盖这条线段的区间的编号。

对于一个询问 $[L,R]$ 若 $f(L,R)$ 包含这条线段，则存在 $x\in S$ 满足 $x\in [L,R]$。

不妨倒过来，对于当前的 $x\in S$，我们让所有满足 $L\le x,R\ge x$ 的二维点 $(L,R)$ 加上点权 $v_i$。

这样显然会算重，因为可能存在  $x,y\in S,x,y\in [L,R]$，这样 $v_i$ 就被算两次以上了。

考虑去重，对于一个询问 $[L,R]$ 让最小的符合条件的 $x$ 产生贡献，即如果同时存在两个 $x,y\in S$ 产生正贡献，就产生一次负贡献。

具体的，我们用 set 来维护 $S$，每次找到 $x$ 的前倾 $y$，让所有满足 $L\le y,R\ge x$ 的二维点 $(L,R)$ 加上点权 $-v_i$。

我们对于每一个线段都要这样做一次，复杂度就爆炸了，考虑对于每一个元素统一算贡献。

考虑第一类正贡献，设 $x$ 在第 $p$ 条线段加入 $x$，第 $q+1$ 条线段离开 $x$。则对所有 $L\le x,R\ge x$ 的点加上 $\sum_{i=p}^q v_i$。

对于第二类负贡献，我们也可以记录每一对前倾后继产生的时间区间 $[p,q]$，然后减去负贡献即可。在加入新的前倾后继关系。

于是我们转化到这样一个问题：

1. 给定若干 $(x,y,v)$，将所有 $L\le x,R\ge y$ 的点 $(L,R)$ 加上 $v$。（这一类操作的数量是 $O(n)$ 的）。

2. 查询满足 $A\le L\le R\le B$ 的所有点权之和。

不妨考虑一个操作 $(x,y,v)$ 对 $[A,B]$ 的贡献，为 $(x-A+1)(B-y+1)v$，令 $A'\gets A+1,B'\gets B+1$，则 $(x-A)(B-y)v=(Ay+Bx-AB-xy)v$。

因为 $A',B'$ 可以看作常数，所以我们做离线二维数点，同时维护 $\sum v,\sum xv,\sum yv,\sum xyv$ 即可。

时间复杂度为 $O(n\log n)$。

Sol 2

将 $[l_i,r_i]$ 称为区间，$[A,B]$ 称为询问。扫描区间的下标。

设当前扫到了 $R$，则当前数组 $v_i$ 表示 $f(i,R)$。则当 $R=B$ 时查询 $[A,B]$ 就是询问所有 $i\in [A,B],v_i$ 的历史和。

考虑如何维护扫描过程中 $v_i$，设 $1\sim R$ 的所有区间中最后一个覆盖线段 $i$ 个编号是 $p_i$，则当前线段 $i$ 会对 $v_{1\sim p_i}$ 做贡献。

每次扫描线的右端点移动，新加入一个区间，会改变一些 $p_i$，设原来 $p_i=x$，后来 $p_i=y$，则这次移动会对 $v_{x+1\sim y}$ 新产生贡献。

每次都是覆盖一段区间，可以用珂朵莉树维护，改变一个颜色段的 $p_i$ 可以用一次区间加完成，而这样的区间加只有 $O(n)$ 次。

然后选择心怡的维护历史和的方法即可，例如维护当前完成的操作数 $T$，当前数组 $A$，设历史和数组为 $B$，再维护一个 $C_i=B_i-A_iT$，则只维护 $A,C$ 即可维护 $B$。

时间复杂度为 $O(n\log n)$。

设往左走的获胜的概率为 $A$，往右走的获胜的概率为 $B$

不难发现，最终的方案里，一定存在一个分界点，分界点左侧的点往左走，右侧点往右走。

特判掉 $a=0,b=0$ 的情况，两侧的问题可以对称为一个子问题。以左侧问题为例。

先枚举一个前缀 $n'$。考虑一个贡献延后计算的东西，维护一个栈，从后往前 dp，每次遇到 $L$ 就塞进栈，遇到 $R$ 就随机栈顶的几个 $L$。最后希望栈里有 $a$ 个 $L$。

设 $f_{i,j}$ 表示考虑了 $i\sim n'$，其中还剩下 $j$ 个 $L$ 在栈里，不难列出转移式：

$$f_{i,j}=\begin{cases}f_{i+1,j-1} & s_{i}=L \\ f_{i+1,j+x}\times B^x\times A & s_{i}=R\end{cases}$$

第二个转移式子表示一个 $R$ 连续击败了 $k$ 个 $L$ 后被一个 $L$ 击败，注意转移中间 $j=0$ 的情况是非法的，需要特判掉。

但是因为我们最终计算答案要枚举分界点，而我们目前的 dp 是确定了一个前缀后再从后往前 dp，考虑到过来，确定了一个前缀后再从前往后 dp。

倒过来后，不难发现我们是让一些 $R$ 和后面的 $L$ 去匹配，但是有 $a$ 个 $L$ 没有匹配，我们把这些没有匹配的 $L$ 放在一边。

设 $f_{i,j}$ 表示考虑了 $1\sim i$ 还有 $j$ 个 $L$ 能放在一边。然后转移都反过来即可。

最后发现转移的这个 $k$ 很没用，用前缀和优化掉即可，时间复杂度为 $O(n^2)$。

# 1 冒泡排序(bubble)

相信大家做过今年的 NOI（2018）。  

众所周知，排列合法当且仅当最长下降子序列不超过 $2$。  

为了方便我们将最长下降子序列的限制变成最长上升子序列的限制。  

特别地 $( a+b=n-1)$ 的情况。  

当 $( a+b<n-1)$ 时，可以将序列和值域都反转，$( a' = n - a - 1, b' = n - b - 1 )$。  

将 \((i, p_i)\) 在平面上画出来，(a, b) 将平面分成了四个区域，不难发现左下和右上不能同时有点。  

假设左没有点，那么左上有 \( a \) 个点，右下有 \( b \) 个点，右上有 \( n - 1 - a - b < 0 \) 个点，不合法。  

不难发现左下的点一定是单调递减的，可以将问题划分成下方和左方两个子问题，相当于要解决 \( b = n - 1 \) 的情况。  

一个合法的序列可以唯一对应一条从 \((0, n)\) 到 \((n, 0)\) 的路径，满足任意时刻 \( x + y \leq n \)，路径长成 \( f(x) = \min_{x \leq y} p_x \) 的形式。  

那么 \( b = n - 1 \) 的情况相当于一个长度为 \( b \) 的合法序列，前 \( a \) 个位置都是前缀最小值。  

前 \( a \) 个位置假设往下走了 \( t(t \geq a) \) 步，  

前面就是方程 \( x_1 + x_2 + x_3 + \cdots + x_a = t \) 的正整数解的个数，就是 $C_{t-1}^{a-1}$。  

后面是从 \((a, b - t)\) 走到 \((b, 0)\) 的方案数，是 $(C_{2b-a-t}^{b-a} - C_{2b-a-t}^{b-a+1})$。  

组合解是相当于从 \( 2b - a \) 个数里面选 \( b \) 个，以第 \( a \) 个数为分界线，枚举左右各有多少个数。  

同理 \(\sum_t C_{t-1}^{a-1} C^{2b-a-t}_{b-a+1} = C_{2b-a}^{b+1}\)。  

对于左方的子问题，将值和值域倒过来就变成下方的子问题了。  

但是这是 NOIP 模拟，所以肯定有更简单的做法。  

我们算左下没有点的情况，那么注意到 \((a, b)\) 这个位置是前缀最小值，那么考虑统计前缀最小值序列个数。  

还是用路径来刻画这个东西，可以发现这个限制等价于 \((a, b)\) 这里的路径是这样走的：\((a, b + 1) \to (a, b) \to (a + 1, b)\)。  

那么两边分开了，用折线法算方案数就行了。

分析

构造方法是：

1.  对于每个点，随机选择一个比其标号小的点作为父亲，生成一棵**递增标号树**。

2. 对上述树的标号打乱。

不难想到，第一步产生的数则种类有 $\prod_{i=2}^{N} (i-1)$ 个，第二步的排列数有 $N!$ 个可能。所以，总方案数为：

$$\prod_{i=2}^{N} (i-1) \times N!$$

关键点来了：有多少种情况可以生成这个树。反向考虑这棵树能怎么生成，也就是存在一种情况得到了一个递增树和一个排列，可以得到这个树。显然，如果一个递增树可以加上某个排列形成这棵树，那么这个排列是唯一确定的。那么，任意一个与输入的树结构相同的递增标号树都可以得到这个树，做一个贡献。如何计算这个贡献？首先，由定义可知 `1` 号节点一定是根，令其 $k$ 个子节点的子树大小分别为 $s_1, s_2, \dots, s_k$，则每个子树分配点集方案树为

$$C_{n-1}^{s_1} \times C_{n-1-s_1}^{s_2} \times \dots \times C_{n-1-\sum_{i=1}^{k-1} s_i}^{s_k}$$

化简可得

$$\frac{N!}{s_1! \times s_2! \times \dots \times s_k!}$$

每个子树同样满足这个标号规则，令 $f(T)$ 为以 $T$ 为根的子树的方案，则：

$$f(T) = \frac{N!}{\prod s_i!} \times \prod f(子树i)$$

展开，化简可得：

$$f(T) = \frac{N!}{\prod sz_u}$$

其中，$sz_u$ 表示树上每个节点的子树大小。这样子我们可以求出来一个节点为根的方案树，接下来我们需要换根。

令 $f_u = \frac{N!}{\prod sz_x},\quad f_v = \frac{N!}{\prod sz'_x}$，从 $u$ 到 $v$ 只会有以下树改变：

$$sz_u = N,\quad sz_v = sz_v$$

$$sz_u' = N-sz_v,\quad sz_v'=N$$

分母产生的变化

$$D_u=(\prod_{x \ne u,v} sz_x) \times N \times sz_v$$

$$D_v = (\prod_{x\ne u,v} sz_x) \times (N-sz_v) \times N$$

比一下，

$$\frac{f_v}{f_u} = \frac{D_u}{D_v} = \frac{N \times sz_v}{(N-sz_v) \times N} = \frac{sz_v}{(N-sz_v)}$$

所以，$f_v = f_u \times \frac{sz_v}{(N-sz_v)}$。

之后我们将其求和，得到总答案数，再逆元除以总情况数即可。

参考代码

#include <cstring>
#include <iostream>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7;
int hd[N], nxt[N * 2], to[N * 2], num = 1;
void add(int u, int v) {
    num++;
    to[num] = v;
    nxt[num] = hd[u];
    hd[u] = num;
}
int sz[N];
void dfs(int u, int fa) {
    sz[u] = 1;
    for (int i = hd[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}
long long fpow(long long x, long long y) {
    long long res = 1;
    while (y) {
        if (y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}
int n;
long long f[N];
void dfs2(int u, int fa) {
    for (int i = hd[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == fa) continue;
        f[v] = f[u] * sz[v] % mod * fpow(n - sz[v], mod - 2) % mod;
        dfs2(v, u);
    }
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        num = 1;
        memset(hd, 0, sizeof(hd));
        for (int i = 1; i <= n - 1; i++) {
            int u, v;
            cin >> u >> v;
            add(u, v);
            add(v, u);
        }
        dfs(1, 0);
        long long fz = 1;  // 分子
        for (int i = 1; i <= n; i++) {
            fz = fz * i % mod;
        }
        long long fm = 1;  // 分母
        for (int i = 1; i <= n; i++) {
            fm = fm * sz[i] % mod;
        }
        f[1] = fz * fpow(fm, mod - 2) % mod;
        dfs2(1, 0);
        long long ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += f[i];
            ans %= mod;
        }
        fm = 1;
        for (int i = 1; i <= n - 1; i++) fm = fm * i % mod;
        for (int i = 1; i <= n; i++) fm = fm * i % mod;
        cout << ans * fpow(fm, mod - 2) % mod << endl;
    }
    return 0;
}