CF1254

CF1254

A

贪心，显然蛇形填数最优。注意特判最后要填完。

173057907

B

贪心，最后的 \gcd 一定是个质数，不妨直接枚举，只有 \omega(\sqrt n) 种。

考虑第 i 条边的贡献至少为 \min{\sum {j=1}^i a_j,\sum{j=i+1}^na_j}，不难发现充分性显然。

所以记个前缀和扫一遍即可。

173059616

C

随意钦定一起点 s 以及另一点，用 n 次叉积可以求得第二个点 p。

n 次求面积，可得出所有 (s,p,i) 的面积，其中面积最大的点一定为 s 的对立点 g。

而同一边的面积一定是有序的。

再用 n 次询问求出每个点在线段 (s,g) 的哪边。

173062577

D

对于点 v 的修改，假定 v 是树根，如果 r 和 u 在同一个子树内，则 v 不在路径上，不会加 d；否则会加上 d。

随机选择一个点，它被加上 d 的概率是 P=\frac{n-sz(u)}n，因此，某个点的权值期望增加量为 P\times d。

很显然可以差分一下。

• 对于重儿子，直接在 BIT 上修改。
• 对于轻儿子，打个标记在父节点上。

查询时加上重链顶的贡献即可。

时间复杂度：O(n\log ^2n)。

173703928

E

如果没有任何限制，答案即为 \prod deg_i!（不同相对顺序）。

限制即为若干条不重叠的路径，故其总长为 O(n)，直接暴力爬树。

对于同一个点可能有若干路径于此交汇，每个点单独考虑则有三种情况：

• 为起始
• 为末尾
• 删 A 后必立刻删 B

设从该点连出的符合条件的链数为 F_i，则答案即为 \prod F_i!。

不合法的情况有：

• 路径重叠
• 路径成环
• 该点需连出的链数超过 1

时间复杂度：O(n)。

173918933