字典序最大的树标号¶
预估时间限制：2.5 秒。内存限制：512 MB。
实际时限以标准程序在目标环境的最慢用例中位时间乘以 \(4\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。
该倍率为静态排序补充解法保留至少两倍实测余量。
背景故事¶
展馆准备在一棵树上挂上亮度各异的灯。每盏灯都要比祖先更亮，同时希望按照结点编号检查时，尽早看到尽可能亮的灯。
(本故事由GPT-6重写)
形式化问题描述¶
给定一棵有 \(N\) 个结点、以 \(K\) 为根的树，结点编号为 \(1,\ldots,N\) .将整数 \(1,\ldots,N\) 各使用一次，给结点赋标号 \(a_1,\ldots,a_N\) .要求每个非根结点的标号严格大于父亲的标号。
在所有合法方案中，使数组 \((a_1,\ldots,a_N)\) 字典序最大：在第一个不同的结点编号处，标号较大的方案更大。
设最优排列的零起算康托排名为
\[
R=\sum_{i=1}^{N} c_i (N-i)!,\qquad c_i=\#\{j:i<j\le N,\ a_j<a_i\}
\]
即将全部 \(N!\) 个排列按字典序升序排列后，它前面有多少个排列。输出 \(R\) 分别对 \(100000007\) 和 \(100000009\) 取模的结果。
输入格式¶
第一行两个整数 \(N,K\) .接下来 \(N-1\) 行，每行两个整数 \(u,v\) ，表示一条树边。
输出格式¶
输出一行两个整数，依次为上述两个模值，不输出标号排列本身。
样例¶
样例 1¶
输入¶
5 1
1 2
2 3
2 5
3 4
输出¶
3 3
样例 2¶
输入¶
5 4
4 2
4 3
4 1
5 4
输出¶
118 118
样例 3¶
输入¶
4 3
3 4
4 1
1 2
输出¶
16 16
样例解释¶
前两组最优标号数组分别为 \((1,2,4,5,3)\) 和 \((5,4,3,1,2)\) ，零起算排名分别为三和一百一十八。第三组是一条以三为根的链，其唯一标号数组为 \((3,4,1,2)\) ，排名十六。
数据范围与保证¶
\(2\le N\le500000\) , \(1\le K,u,v\le N\) . 输入边恰好构成一棵树。
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |