这谁能想到啊
CF1844G
大意：给一棵树，与所有点 \(i\) 到点 \(i+1\) 的距离 \(d_i\)，要求还原出边权。\(n\le 10^5\)。
毫无道理的，记 $dis_{i,k}$ 为 $1$ 到 $i$ 距离在模 $2^k$ 意义下的值。注意到 $d_i\equiv dis_{i,k}+dis_{i+1,k}-2dis_{lca(i,i+1),k}\equiv dis_{i,k}+dis_{i+1,k}-2dis_{lca(i,i+1),k-1}\pmod {2^k}$。由此可以递推出 $dis_{i,k}$。$k$ 足够大时即可以视作真实的值，因此复杂度 $O(n(\log n+\log V))$。
妙处在于通过考察模 \(2^k\) 次方意义下的值消除了后效性。