problem
一棵树边带正整数权，给出所有 \(dis(i,i+1)\)，还原树的边权，或者无解。\(n\leq 10^5,V\leq 10^{12}\)。
solution
首先很容易得到 \(n\) 个方程形如 \(dep_1=0,dep_i+dep_{i+1}-2dep_{lca(i,i+1)}=d_i\)，我们想解这个方程，但是好像很难解，因为有三项。
因为这个 \(dep_i\) 全部为非负整数，考虑这么一个神奇的事情就是将所有方程左右两边对 \(2\) 取模，这样没有了 \(-2dep_{lca(i,i+1)}\) 这一项，我们可以直接递推得到所有 \(dep_i\bmod 2\) 的值，然后将这一位的影响去掉，继续对 \(4\) 取模，对 \(8\) 取模……对 \(2^{40}>10^{12}\) 取模，这还不行，有进位，再处理 \(17\) 位，即可。
code
点击查看代码
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
template<int N,int M,class T=int> struct graph{
int head[N+10],nxt[M*2+10],cnt;
struct edge{
int u,v;T w;
edge(int u=0,int v=0,T w=0):u(u),v(v),w(w){}
} e[M*2+10];
graph(){memset(head,cnt=0,sizeof head);}
edge&operator[](int i){return e[i];}
void add(int u,int v,T w=0){e[++cnt]=edge(u,v,w),nxt[cnt]=head[u],head[u]=cnt;}
void link(int u,int v,T w=0){add(u,v,w),add(v,u,w);}
};
int n,dep[1<<17],fa[18][1<<17],p[1<<17],x[1<<17];
LL d[1<<17],ans[1<<17];
graph<1<<17,1<<17> g;
void dfs(int u,int f){
fa[0][u]=f,dep[u]=dep[f]+1;
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v; if(v==f) continue;
dfs(v,u);
}
}
int lca(int u,int v){
if(dep[u]<dep[v]) swap(u,v); int d=dep[u]-dep[v];
for(int j=17;j>=0;j--) if(d>>j&1) u=fa[j][u];
if(u==v) return u;
for(int j=17;j>=0;j--) if(fa[j][u]!=fa[j][v]) u=fa[j][u],v=fa[j][v];
return fa[0][u];
}
int main(){
// #ifdef LOCAL
// freopen("input.in","r",stdin);
// #endif
scanf("%d",&n);
for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),g.link(u,v);
for(int i=2;i<=n;i++) scanf("%lld",&d[i]);
dfs(1,0);
for(int j=1;j<=17;j++) for(int i=1;i<=n;i++) fa[j][i]=fa[j-1][fa[j-1][i]];
for(int i=2;i<=n;i++) p[i]=lca(i-1,i);
//ans[i]+ans[i+1]-2[ans[y[i]]=d[i]
//ans[1]=0
for(LL t=0;t<=60;t++){
for(int i=2;i<=n;i++) x[i]=(d[i]&1)^x[i-1],ans[i]+=(LL)x[i]<<t;
for(int i=2;i<=n;i++) d[i]-=x[i]+x[i-1]-2*x[p[i]],d[i]>>=1;
}
for(int i=1;i<=n;i++) if(d[i]) return puts("-1"),0;
vector<LL> h; h.reserve(n-1);
for(int i=1;i<=g.cnt;i+=2){
int u=g[i].u,v=g[i].v;
if(dep[u]<dep[v]) swap(u,v);
h.push_back(ans[u]-ans[v]);
}
if(*min_element(h.begin(),h.end())<=0) puts("-1");
else for(LL x:h) printf("%lld\n",x);
return 0;
}