A
已知 \(n\) 边形的一个三角剖分，你可以进行若干次“城市建造”操作，可以选择三个点并新建一个点为这三个点的内心并连边。构造方案，使得城市建造次数最少，且新图可以划分为两棵树。
只需要进行一次城市建造操作，就可以使边数变为 \(2n\)，点数为 \(n+1\)，显然即可划分。
考虑取出一个三元环，要求有两条边是多边形边，操作后形成四个点的团，把这个团的边分配好。
对于外面的考虑每次删一个度数为 \(2\) 的点，两条边分属两棵树。类似拓扑排序。
B
有 \(n\) 个点排成一列，执行 \(q\) 次修改每次区间加，最后形成序列 \(A\)。在 \(i\) 点可以跳跃至 \(i+k\)，贡献为 \(a_i\)，或走向 \(i+1\)，没有贡献，问从 \(1\) 到 \(n\) 贡献最大多少。\(n,k\le 10^{12},q\le 2.5e5\)。
离散化划分为若干个权值相同的段，贪心地，要么是取段的开头，要么是接在上一个跳 \(+k\)。
所以对于每个段，只需要知道其左端点前 \(k\) 的位置的信息，以及往前信息的最大值即可。
考虑线段树维护所有同余 \(k\) 的信息，支持区间加，单点取 \(\max\) 即可。
C
一棵树，一开始 \(0\) 号点有病毒，每个点有人，每个人的活动范围是距离其不超过 \(p_i\) 的点。两个点活动范围有交集，就可以在有交集的地方传播病毒。每个点传播病毒的时间是 \(C_i\)，问每个点被传播到的时间。
考虑点分治处理。对于分治中心，求出所有点到中心的距离，然后前缀优化建图即可。
这是一个套路题，可以与点分树联系起来。
D
一棵树边权为 \(1\)，你可以通过若干次询问来找到所有的边，单次询问是询问 \(ask(u,S)\) 表示查询 \(u\) 到 \(S\) 集合里所有点的距离之和。要求询问次数 \(\le 8500\)，\(\sum |S|\le 3e5\)。\(n\le 1000\)。
一个想法就是每次找重心出来，然后做点分治。重心的性质就是到每个点的距离之和最短。
重心的儿子距离其为 \(1\)，然后一个个点去确认其属于重心的哪个儿子。考虑用集合的二分去处理。
所以一层的询问次数是 \(O(n\log n)\)，总共有 \(O(\log n)\) 层，总的为 \(O(n\log ^2n)\)。\(\sum |S|\) 应是 \(O(n^2)\) 级别。
另一个想法就是定一个根然后一层一层确定两层之间的边。假设现在确定 \(A\) 到 \(B\) 的边，\(A\) 是较浅的。
考虑把 \(A\) 随机对半分成两份为 \(A_1,A_2\)。
考虑调用 \(ask(B_i,A_1),ask(B_i,A_2)\)，那么 \(ask(B_i,A_{1/2})=ask(fa_{B_i},A_{1/2})+|A_{1/2}|\)。
那么很显然我们可以按照 \(ask(fa_x,A_1)\) 的值分类，对于分在不同类的 \(B_i\)，他们的父亲势必不同。
现在我们就考虑把父亲也分类，直接调用 \(ask(A_i,A_1)\) 分类即可。对于分的每一类考虑继续分治下去。
这个题充分考察了集合的二分，以及通过随机化来给分治划定标准。