CF1844G Tree Weights 做题记录

给定一棵 $n$ 个点的无根树，每条边有一个未知的正整数边权。

对于所有的 $1 \le i < n$，给出点 $i$ 到点 $i + 1$ 的距离 $d_i$，请还原出任意一组合法的边权，可能无解。

$2\le n\le 10^5$，$1\le d_i\le 10^{12}$。

逐位确定。

令根为点 $1$，设 $dep_{u}$ 为 $u$ 到根的距离，那么有 $d_i=dep_{i}+dep_{i+1}-2dep_{lca}$，并且我们已知 $dep_1=0$。

注意到 $2dep_{lca}\equiv 0\pmod 2$，所以可以知道 $dep_i\text{ mod }2$；然后注意到 $2dep_{lca}\text{ mod }4=2(dep_{lca}\text{ mod }2)$，所以接下来就可以知道 $dep_i\text{ mod }4$ ……

这启发我们从小到大枚举 $k$，依次确定 $dep_{i}\text{ mod } 2^k$。

由于 $d_i\le 10^{12}$，所以 $dep_i\text{ mod }2^{60}=dep_i$，再做一次 dfs 即可知道边权。

注意若求出的边权 $\le 0$ 或 $2dep_i>2^{60}$ 则无解。

时间复杂度 $O(n\log V)$，代码如下：

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int S=100005,BS=25,B=60;

int n;
vector<pair<int,int>> g[S];
long long a[S];
int dep[S],fat[S][BS];
int b[S];
long long tmp[S],res[S],ans[S];

void dfs(int u,int fa)
{
	dep[u]=dep[fa]+1;
	fat[u][0]=fa;
	for(int i=1;i<=BS-3;i++) fat[u][i]=fat[fat[u][i-1]][i-1];
	for(auto v:g[u]) if(v.first!=fa) dfs(v.first,u);
}

inline int getlca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=BS-3;i>=0;i--) if(dep[fat[x][i]]>=dep[y]) x=fat[x][i];
	if(x==y) return x;
	for(int i=BS-3;i>=0;i--) if(fat[x][i]!=fat[y][i]) x=fat[x][i],y=fat[y][i];
	return fat[x][0];
}

void getans(int u,int fa,int faid)
{
	if(faid!=0) ans[faid]=res[u]-res[fa];
	for(auto v:g[u]) if(v.first!=fa) getans(v.first,u,v.second);
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back(make_pair(y,i)),g[y].push_back(make_pair(x,i));
	}
	for(int i=1;i<=n-1;i++) scanf("%lld",&a[i]);
	dfs(1,0);
	for(int i=1;i<=n-1;i++) b[i]=getlca(i,i+1);
	for(int i=1;i<=B;i++)
	{
		long long pre=1ll<<i;
		for(int j=1;j<=n-1;j++) tmp[j+1]=((a[j]+2*res[b[j]]%pre-tmp[j])%pre+pre)%pre;
		for(int j=1;j<=n;j++) res[j]=tmp[j];
	}
	for(int j=2;j<=n;j++) if(res[j]==0||2*res[j]>(1ll<<B)) return puts("-1"),0;
	getans(1,0,0);
	for(int i=1;i<=n-1;i++) if(ans[i]<=0) return puts("-1"),0;
	for(int i=1;i<=n-1;i++) printf("%lld\n",ans[i]);
	return 0;
}