T1 美丽校园
标准解法
很容易想到：从 \(1\) 出发向 \(t\) 走的路径不容易得到，而从 \(t\) 向 \(1\) 的路径只需要每次走到当前点的父节点。
因此问题转化为：
求从 \(t\) 向根节点走 \(dis_t - \frac{d}{2}\) 能到达的最远位置。
若最后走到点 \(x\) 上，则 \(x\) 即为答案，若最后走到一条边 \(e: x \rightarrow pnt_x\) 上，则 \(pnt_x\) 即为答案。
其中： \(dis_t\) 表示从 \(t\) 到 \(1\) 的距离，\(pnt_x\) 表示 \(x\) 的父节点。
预处理出 \(f_{p,i}\) 表示节点 \(p\) 的 \(2^i\) 辈祖先和 \(d_{p,i}\) 表示 \(p\) 到 \(f_{p,i}\) 的距离，倍增求解即可。
时空复杂度
时间复杂度：\(\mathcal{O}\left(\left(n+m\right)\log n\right)\)
空间复杂度：\(\mathcal{O}\left(n\log n\right)\)，常数约为 \(2\)
特殊性质与部分分
前 60%
时间复杂度小于等于 \(\mathcal{O}\left(nm\right)\) 的暴力能够通过。
特殊性质 1
「图是 \(1\) 为一个端点的链」，将树上问题弱化为序列问题。
特殊性质 0,2
「图随机生成」或「图是 \(1\) 为根的满二叉树」，树的深度为 \(\log n\) 级别，时间复杂度小于等于 \(\mathcal{O}\left(m\cdot\max\left(depth\right)\right)\) 的暴力能够通过。
T2 生成序列
60分做法
60分的\(O(n^3)\) DP应该是比较好写, 略
标准解法
考虑固定一个 \(T_n\)，求出包含其的 \(n\) 元组数量。
对于 \(T_n\) 中的每一个元素，可以发现其与若干个元素形成了依赖关系，并且其可以简化为一棵树。具体而言：
- 对于一个 \(1\) 或 \(m\)，其依赖左边最后一个 \(1\) 或 \(m\)；
- 对于其它合法值，其依赖右边第一个 \(1\) 或 \(m\)；
因为 \(n\) 元组数量即为生成 \(T_n\) 的方案数，所以其等同于依赖关系树的拓扑序数量。一棵树的拓扑序数量为 \({siz_{root}! \over \prod siz_u}\)，因为对于每一个节点 \(u\)，其排在其子树中的节点前面的概率为 \(1 \over siz_u\)。
然后可以用一个 DP 求出所有 \(T_n\) 的方案数之和。设 \(f_i\) 表示当前考虑到 \(i\) 且末尾元素为 \(1\) 或 \(m\) 的方案数，转移分两种，一种是从 \(i-1\) 转移过来，另一种是从 \(j(\le i-2)\) 中间插入一些数，方程较简单，留给你自己思考 (想不通再看 std)。时间复杂度 \(\Theta(n^2)\)。
T3 奶茶分配
标准解法
线段树维护矩阵乘法，Plozia在线段树总结里写得很清楚, 好好看看题解 哈
https://www.cnblogs.com/Plozia/p/16142252.html
T4 吃豆豆
CCPC-Wannafly Winter Camp Day1 B题吃豆豆，wls出的题，当时wls来义乌中学讲了这题感觉很不错
30分解法
如果你上网搜一下这题的题解，基本上都是 30分的做法，暴力跑DP，状态定义如下：
定义状态 f[i][j][t] 表示在t秒时 i，j位置最多可以获得的豆豆数量，
标准解法
C 这里很大，\(10^{18}\), 显然跟 时间有关的状态基本上就寄了
仔细观察 \(T_{i, j}\) 最大是10， 而 1， 2， 3， 4， 5， 6， 7， 8， 9， 10 的 LCM 只有2520
所以我们对时间每 2520 进行分段，显然 dp的状态只需要求解 f[i][j][t <= 2520] 即可。
那么 S -> T 的路径就可以拆分成 S -> M (经过2520的整数倍 E 秒)，再由 M -> T
那么我们预处理
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= N; ++j) M[0][i][j] = f[i][j][2520];
M[i] 表示 时间过了 \(2^i\) 倍的 2520， 任意两点i 到 j 最多吃到的糖果数量
通过倍增我们可以计算出 M[1], M[2], M[3] .... M[51]
最后一步通过倍增 和 枚举剩余时间 （不足一个2520的）来确定答案
for (int i = 51; ~i; --i) {
tmp = R * M[i];
if (tmp[S][T] < C)
R = tmp, ans += 1ull << i;
}
for (int i = 1; i <= 2520; ++i)
for (int j = 1; j <= N; ++j)
if (f[j][T][i] > 0)
if (R[S][j] + f[j][T][i] >= C)
return printf("%llu\n", ans * 2520 + i), 0;