比赛链接:AGC005
(刷新以获取数学公式)
C. Tree Restoring
题意
给出树上每个节点到其它节点的最远距离，问是否可能。
\(n ≤ 100\)。
题解
离一个点最远的节点是直径两端点之一。
先把直径上的点切出来。剩余的点判断一下是不是在 \(\lceil \frac{d}{2} \rceil +1\)和 \(d + 1\)之间即可。
D. ~K Perm Counting
题意
计数\(n\)个数全排列个数，使得\(abs(a_i - i) ≠ K\)
\(2 ≤ N ≤ 2000， 1 ≤ K ≤ N − 1\)。
题解
不妨先考虑 \(K = 1\) 怎么做。
记恰有 \(i\) 个位置不合法的方案数为 \(f_i\), \(g_i\)为有不少于\(i\)个位置不合法，但是恰有 \(j\) 个位置不合法的情况会被算 \(\dbinom{j}{i}\) 次的方案数。
于是有 \(g_i = \sum_{j = i}^{n} \dbinom{j}{i} f_j\)
二项式反演得 \(f_i = \sum_{j = i}^{n} (-1)^{j - i} g_j\)
我们要计算的就是 \(f_1\)
考虑 \(g\) 如何计算。 \(g_i\) 实际上是钦定 \(i\) 个位置不合法，其余位置随便放的方案数。
\(dp_{i, j, a, b}\) 表示前 \(i\) 个数， 已经钦点了 \(j\) 个位置不合法， \(i\) 和 \(i + 1\) 有没有被用于钦定。
转移有三种情况:不钦定；钦定\(i+1\)的位置放\(i+2\)；钦定\(i+1\)的位置放\(i\)。注意如果是不钦定，我们不用理会\(i+1\)这个位置放了什么数。因为如果我们最终钦定了\(j\)个数，我们认为剩下\(n-j\)个数可以随意放置。
于是我们得到 \(g_i = (n - i)! dp_{n, j, 0/1, 0}\)
当 \(K ≠ 1\)的时候，我们对序列做一点处理：把所有模 \(K\) 相同的数放在一起。除了有些位置放\(i+1\)是合法的，其余的情况和\(K=1\)相同。
E. Sugigma: The Showdown
题意
给定 \(n\) 个节点， \(n-1\)条红边和\(n-1\)条蓝边。红边和蓝边分别组成一棵树。A从点X出发，只能走红边；B从点Y出发，只能走蓝边。两人轮流走，可以不走，当两人走到同一点时游戏结束。A先走且要最大化游戏步数；B后走且要最小化游戏步数。输出游戏结束时进行的步数。如果不会结束输出-\(1\)。
\(2 ≤ N ≤ 200000\)。
题解
这题的关键在于：游戏是否结束取决于A是否能走到一条红边\((u, v)\)的端点，且\(u, v\)在蓝树上的距离不小于\(3\)。
如果能走到，A可以在这两条边来回走，B永远抓不到它。
如果不能走到，能使用的红边连接蓝树上距离不超过\(2\)的点。A无法离开B所在的子树。这时A会跑到一个能跑到且离Y最远的点等死。
F. Many Easy Problems
题意
给定 \(n\) 个点的树，对于每个\(k\)，对于每种选择\(k\)点的方案，求出包含这\(k\)个点最小导出连通子图点数之和。
\(2 ≤ N ≤ 200000\)。
题解
考虑每个点对\(ans_k\)的贡献。
不妨设根为\(u\)，选出\(k\)个点后，点\(u\)在子图中，当且仅当\(k\)个点的LCA为\(u\)。
如果\(u\)孩子的子树大小分别为\(size_1, size_2, .. size_m\)，那么\(u\)对\(ans_k\)的贡献是\(\dbinom{n}{k} - \sum_{i=1}^{m}\dbinom{size_i}{k}\)
记以\(1, 2, .. , n\)为根时，\(size = i\)的子树个数和为\(cnt_i\)，那么
\[ans_k = n\dbinom{n}{k} - \sum_{i = 1}^{n} cnt_i\dbinom{i}{k}\\ =n\dbinom{n}{k}-\frac{1}{k!}\sum_{i = 1}^{n}cnt_i*i!*\frac{1}{(i-k)!}\]这样就可以NTT优化了。