思路 显然我们需要求出原树的最大匹配。 定义 dpi,0/1dp_{i,0/1}dpi,0/1​ 表示在 iii 为根的子树中进行匹配，且 iii 不选/选 的最大匹配。状态转移方程比较显然： {dpu,0=∑valvdpu,1=(∑valv)−valt+dpt,0+1\left\{\begin{matrix} dp_{u,0} = \sum{val_v}\\ dp_{u,1} = (\sum{v

思路 观察到 ai,bi≤na_i,b_i \leq nai​,bi​≤n，又要求 ai×aj=bi+bja_i \times a_j = b_i + b_jai​×aj​=bi​+bj​ 的数量，那么显然有 ai×aj=bi+bj≤2na_i \times a_j = b_i + b_j \leq 2nai​×aj​=bi​+bj​≤2n。 并且显然有 aia_iai​ 和 aja_jaj​ 其

思路 首先考虑答案下界，因为 (n−i)(n - i)(n−i) 和 ∣di+i−n∣|d_i + i - n|∣di​+i−n∣ 均大于等于 000，所以它们相乘一定大于等于 000。于是考虑能不能构造出结果为 000。 显然当 i=ni = ni=n 时，无论 did_idi​ 的值是什么，式子的结果为 000。因此只需要考虑 i∈[1,n)i \in [1,n)i∈[1,n) 的情况。 因为

模拟赛怒码 7KB 错解，赛后 10min AC。 思路 首先观察 l,rl,rl,r 不同的关系对于结果的构成有什么影响，记 gf=LCA(l,r)gf = LCA(l,r)gf=LCA(l,r)。 l=rl = rl=r。很显然，答案就是以 lll 为根的节点的深度和。 gf≠l∧gf≠rgf \neq l \wedge gf \neq rgf=l∧gf=r。在 lll 子树中的节

谁说平衡树过不了。 思路 思路就简单说了，主要讲一下卡常技巧。 5×1055 \times 10^55×105 范围内的数约数最多有 200200200 个约数。于是考虑用平衡树维护。 在 aia_iai​ 所有约数所对应的平衡树中插入一个 iii。然后在 iii 这个平衡树中，将 [l,r][l,r][l,r] 区间 split 出来，就得到了我们需要的这个子树，同时筛掉 k∤aik \nmid

思路 首先先把原式中的 C(i,k)C(i,k)C(i,k) 化出来： C(i,j) mod j=Ajij mod j=i(i−1)⋯(i−j+1)j mod j=((j−1)!×⌊ij⌋) mod jC(i,j) \bmod j = \frac{A^i_j}{j} \bmod j = \frac{i(i - 1)\cdots(i - j + 1)}{j} \bmod j = ((j - 1)!

思路 有加边操作，一眼 LCT。问题在于处理询问操作。 首先，判断联通。如果 x,yx,yx,y 不在同一个联通块内，则一定没有答案。 其次，求出 x,yx,yx,y 之间节点的数量 numnumnum（包括 x,yx,yx,y）。如果 num=3num = 3num=3 说明 x,yx,yx,y 之间有一个共同的节点；如果 num=2num = 2num=2 说明 x,yx,yx,y 直接连接；

思路 因为石头的数量太多的不好维护，于是我们转化参照物，直接看作人在动。 那么，人向下走相当于向下走两步，向上走相当于不走，向右走相当于向右下走。 然后直接暴力 BFS 一下，算出走到最后一列的时间，然后将终点按照时间找到转化参照物后的位置，取最小值即可。 Code 123456789101112131415161718192021222324252627282930313233343536373

思路 首先我们发现，刚开始人需要走到箱子周围的四个位置。其次我们发现人需要站的位置最多有两个。 例如，ccc 在 bbb 左方，人就需要在箱子右方。 然后我们就可以算出 aaa 点走到这两个点的距离，需要注意的是，这两点所产生的贡献不一定是两点间的曼哈顿距离，因为如果 bbb 挡在了 aaa 和该点之间，贡献需要加 222。 接着我们选择走最近的点，然后发现如果不考虑后续转向的贡献，距离就是 b,

拜谢 ssxvngn。 思路 对于 gcd⁡(ai,aj)\gcd(a_i,a_j)gcd(ai​,aj​) 的贡献次数为：∑k=j+1n[ak≥max⁡(ai,aj)]\sum_{k = j + 1}^{n}[a_k \geq \max(a_i,a_j)]∑k=j+1n​[ak​≥max(ai​,aj​)]。 因为原式本质是取序列中任意三个元素 a,b,ca,b,ca,b,c 做 fff 函数，