CF1844G 题解

鉴定为学 MO 学的。

MO 中著名的《数学奥林匹克小丛书高中卷》的第十五本曾经讲过，如果原方程较难解，可以考虑给左右两边同时对 \(M\) 取模，然后研究取模以后的问题，其中 \(M\) 为一个根据问题选取的适当的整数。

我们看见这个问题觉得很烦，因为大家都能发现这个条件给的相当于 \(d_i+d_{i+1}-2d_{lca(i, i +1)}=???\)，左边有一个 \(\times2\)，所以选取 \(M=2^k\) 是合适的。

相信想到这里这道题已经可以做完了，我们取 \(k=1,\dots,60\) 然后分别对方程左右两边模 \(2^k\)，然后递推。因为左边有 \(\times 2\)，所以求出所有 \(d_i\bmod2^{k-1}\) 的同时，也对 \(2^{k}\) 有了贡献。根据这样的思想可以做完这题。更详细的推导已由其他题解给出，不再赘述。