CF884G Tree Wights

CF884G Tree Wights

给定一棵 \(n\) 个点的树，给定 \(d_1,d_2,\cdots,d_{n-1}\)，其中 \(d_i\) 表示 \(i\) 到 \(i+1\) 在树上简单路径的距离，问能否构造每条边的边权都是正整数，并构造一种解。
\(2\le n\le 10^5\)，\(1\le d_i\le 10^{12}\)。

本题难点在于两次转化。

首先，如果题目中的距离距离不是加法距离，而是 xor 距离，问题就变得简单了。

具体的，我们可以首先求出 \(1\) 与任意一点的距离 \(w(1,i)=\bigoplus_{j=1}^{i-1}d_j\)，然后就相当于求出了 \(1\) 与每个邻点的之间的边权，然后又可以求出每个邻点与其邻点的边权，往下递推。

第二，考虑 xor 与加法的关系，xor 与加法是模 \(2\) 同余的，那么可以对 \(d\) 从低到高二进制下按位考虑，每次做一遍上面的问题，然后通过倍增可以求出任意 \(i\) 与 \(i+1\) 之间的距离，用 \(d_i\) 减去这个距离，删掉最后一位继续处理即可。

时间复杂度 \(O(n\log n\log V)\)。