CF1844G Tree Weights

Alex_Wei · 2023-07-14 12:18:24 · 题解

CF1844G Tree Weights

阴间 ad-hoc 构造。

以 1 为根，设 x_i 为 i 的深度，则 x_i + x_{i + 1} - 2x_{u_i} = d_i，其中 u_i 是 i 和 i + 1 的 LCA。

首先已知 x_1 = 0，考虑递推 x_{i + 1} = d_i + 2x_{u_i} - x_i。

可以按位确定：在模 2 意义下递推 x_{i + 1} = d_i - x_i，得到 x_i\bmod 2 的值；在模 4 意义下递推 x_{i + 1} = d_i + 2(x_{u_i}\bmod 2) - x_i，得到 x_i\bmod 4 的值，以此类推，直到求出在模 2 ^ {60} 意义下的 x 即为真实值。

最后检查是否合法即可：每个点的深度大于其父亲，且 x_i + x_{i + 1} - 2x_{u_i} = d_i。

时间复杂度 \mathcal{O}(n(\log n + \log V))。代码。