CF1746D
Solution ：
设 {\rm s}(x) 表示 x 的儿子数量
因为对于u的两个儿子的量 g_v,g_{v'},|g_v-g_{v'}| \leq 1，因此 \begin{aligned}\forall v, g_{v} \in \{\lfloor\frac{g_u}{ {\rm s}(x)}\rfloor, \lceil\frac{g_u}{{\rm s}(x)}\rceil\}\end{aligned}，对于 g_u 又有两个取值，因此 g_v 一共有 4 个可能的取值。由 \begin{aligned}\lfloor \frac{a}{bc}\rfloor = \lfloor \frac{\lfloor \frac{a}{b} \rfloor}{c} \rfloor\end{aligned} 等结论可以证明(也可以不用) 上述上述四个取值 ⌊x/num⌋, ⌈x/num⌉, ⌈(x+1)/num⌉,⌊(x+1)/num⌋ 只有两种可能。因此进行\rm dp的总状态量是 O(n) 的。
标记为f_{u,0},f_{u,1}，设{\rm dp}_{u,0/1}表示u子树内按照下/上取整时(量为f_{u,0/1})的最大收益。
设一共要取 a 个 1 和 b 个 0 , 考虑 {\rm dp}_{v}, {\rm dp}_{v'} 两者分别取 0, 1 ，如果交换两者的选择更优，当且仅当 {\rm dp}_{v,1}+{\rm dp}_{v',0}>{\rm dp}_{v',1}+{\rm dp}_{v,0}，即 {\rm dp}_{v,1}-{\rm dp}_{v,0} 更大的优先级更高(选择 1)，直接排序即可。
那么转移只需要满足 \begin{aligned}\sum_{}f_{v,x}=f_{u,i}\end{aligned} 就可以了，倒序枚举 j 使得 j\times f_{v,1}+({\rm s}(x) - j)\times f_{v,0} = f_{u,i}，就是需要的 1 的数量。
CF1735E
Solution :
考虑钦点两个屋之间的距离 L ，得到这个 L 首先有个比较朴素的暴力，可以枚举 \rm d_{1,i}, d_{2,j} 进行匹配，匹配量是 O(n^2) 的。但是显然如果有解，那么每一个 d_{1,i} 一定能匹配一个 d_{2,j} ，那么强行让 d_{1,1} 做匹配：假设屋的坐标分别是 x,y ，那1这个建筑有 3 种可能：[0,x],(x,y),[y,\rm lim]，对于左右两种，就是 |d_{1,1}-d_{2_i}|，中间这种就是 d_{1,1}+d_{2,j}，这样就把可能的距离限制为了 2n 种。
假设现在枚举的钦点距离是x，如何判断当前距离合法？
设 d_{1,1} 是左边的屋，那跟他做匹配的 d_{2,j} 一定在他的右边。如果某点跟 1,1 的距离比跟 2, j 的距离小并且和 2,j 的距离大于 x 显然这个点在 1, 1的左边；如果某点与 1, 1 2, j 的距离和为 x 显然这个点在中间；如果某个点跟 2,j 的距离小于跟 1, 1 的距离，并且和 1,1 的距离大于 x 显然这个点在 2, j 的右侧。
直接把最左侧的点设为0坐标即可。