大工之星题解
难度梯度（估计）：A<B<C=D=E
-
A
输出三个数的
max乘以2 即可 -
B
动态规划,由于 n,m,k状态都很小，使用最朴素的dp就可以通过。
关于袋鼠数量的值域，思考后会发现根本跑不满100*100，大概在1e3这个数量级就不会增长了，所以多测下复杂度是正确的。
虽然我验题的时候读题没太遇到困难，但是本题似乎有题面不清的问题，这里狠狠谴责某造题人（不是）。
-
C
对于询问1：答案即为两点间路径的长度
对于询问2：使用树形dp维护
\sum sonsize，\sum sonsize^2 ，简单加减即可实现O(1) 查询对于询问3：可以想到只有x到u方向，x到v方向的两坨子树不能成为答案，于是问题转化成了求 x 到某点的唯一路径上距离 x 最近的点是什么。 求两次 lca 分类讨论+任意方式（譬如倍增，树剖，长链剖分等）求树上第 k 级祖先即可，单次复杂度仍然是
O(\log n) 。 -
D
发现两个操作都需要按照顺序做且仅做一次，于是不妨分类讨论。
case1：第一次交换的两点都在第二次选择的区间内/都在第二次选择的区间外。 此时第一次操作完全不起作用，线性做前缀和查找一下最优解即可。
case2：第一次交换的两点分别在第二次操作选择的区间内/外，即一个点在内部，一个点在外部。按照区间外部的点在区间内部点的 左/右 侧再进一步分类讨论，每种情况依然可以线性求解。
整体时间复杂度
O(n) 本题为了保证符合正解的 python 代码可以通过，也放掉了一些小常数的
O(n \log n) 做法。 -
E
发现固定左端点之后，右端点从左往右移动时区间gcd整体变化次数不超过
\log(值域) 次，这个结论在辗转相除的角度很好证明。于是可以对每个左端点都点都把这
\log 个右端点反复二分处理出来（每次二分需要判断区间gcd是否不变，这里需要一个能快速查询静态区间gcd的数据结构，譬如ST表），并固定左端点计算贡献，开一个map存答案就好。时间复杂度
O(n \log^3 n) 好像比赛期间有些奇怪的东西也通过了这道题，
我们有理由怀疑有些是GPT（？）