A. [八省联考 2018] 林克卡特树
注意到题目等价于在一棵树上选出恰好 �+1 条点不交的链，并最大化所有链的权值和
考虑 wqs 二分，每选出一条新的链就赋 Δ 的额外权值，树形 dp 算出取得最大权值时分割的链数，二分 Δ 即可
树形 dp 时记录每个点是单链还是链的 LCA，分别记为 ���,1,���,2 转移即可
时间复杂度 �(�log�)，其中 �=∑|��|
B. [国家集训队] Crash 的文明世界
先考虑 �=1 的情况，我们只需要换根 dp 即可，但当 �>1 时，换根的转移需要我们从 ∑�dist(�,�)� 快速转移到 ∑�(dist(�,�)+1)�，用二项式定理展开，维护 0 次方和到 � 次方和，单次转移需要 �(�2) 的时间复杂度，无法通过此题
考虑优化，注意到问题主要在 (�+1)�−�� 不好维护，考虑下降幂的性质：(�+1)�―−��―=�×��−1―，这样维护 ∑�dist(�,�)0―∼∑�dist(�,�)�―，即可做到 �(�) 转移
最后求答案时用一般幂的展开公式 ��=∑�=0�{��}��―，预处理出第二类斯特林数的前 � 行即可
时间复杂度 �(�2+��)
C. [NOI 2020] 美食家
考虑作出邻接矩阵，用 (max,+) 卷积求出邻接矩阵的 � 次方，但我们发现边权的限制很难处理，于是考虑拆点，在一条长度为 �� 的边中间插入 ��−1 个节点，但这样显然会超时，考虑对每个节点 � 拆点，用状态 (�,�) 表示 � 天后能到达 �，然后直接矩阵快速幂优化即可
但注意到此时的时间复杂度是 �((��)3�log�) 会超时，注意到不需要计算出邻接矩阵，我们只需要求出从 1 开始到每个状态的权值即可，因此考虑优化成向量左乘转移矩阵的形式，因此我们预处理出转移矩阵的 2� 次方，每次只需要用向量乘转移矩阵即可
时间复杂度 �((��)3log�+(��)2�log�)
D. [联合省选 2020] 作业题
考虑先推式子，设 �(�) 表示 gcd(��1,��2,…,���−1)=� 的方案数，显然答案即为 ∑�=1∞�×�(�)，考虑莫比乌斯反演，记 �(�) 表示 �∣gcd(��1,��2,…,���−1) 的方案数，显然有 �(�)=∑�∣��(�)，莫比乌斯反演得 �(�)=∑�∣��(�)×�(��)，因此我们只需要求每个 �(�)，就可以在 �(�ln�) 的时间复杂度内反演得到 �(�)
显然求 �(�) 只需要把 �∣�� 的每个 �� 加入边集 ��，然后求 ��=(�,��) 的生成树边权之和，显然生成树的边权积之和可以直接用矩阵树定理，考虑构造二项式 ���+1 作为新的边权，在 mod�2 意义下求出其 Kirchoff 矩阵 �� 的行列式值，其常数项系数即为答案
注意到此时的时间复杂度为 �(��3)，但显然对于很多 �，其 Kirchoff 矩阵不是满秩的，此时无法找到生成树，�(�)=det(��)=0，可以直接判掉，先用并查集判断图是否联通再求 det(��)
由于每条边至多出现在 � 个 �� 中，而 �(�) 有意义必须保证 |��|≥�−1，因此有意义的 � 只有 �(���) 个，因此时间复杂度为 �(�2��)
