ARC103F Distance Sums 题解

ARC103F Distance Sums

题意

• 有一棵 $n$ 个点的树。
• 对于每个点 $i$，已知 $d_i$，表示 $\sum_{j=1}^n \operatorname{dist}(i,j)$。
• 所有 $d_i$ 两两互不相同。
• 构造出一棵符合要求的树，或者判断无解。
• $n \le 10^5$。

题解

首先这棵树只有一个重心，否则这两个重心的 $d$ 值相同，且这个重心一定是 $d$ 值最小的点。

以重心为根，有每个非根节点 $x$ 满足 $d_x > d_{f_x}$，其中 $f_x$ 表示 $x$ 的父亲。

按照 $d$ 值从大到小考虑每个点 $u$，则相当于每次剥去一个叶子，且与 $u$ 相连的一定是 $d$ 值为 $d_u - n + 2s_u$ 的点 $v$，其中 $s_u$ 表示 $u$ 的子树内点的个数，需要动态维护。

重复 $n-1$ 次这个过程后即可确定这棵树的形态，最后检查一下重心的 $d$ 值是不是对的就可以了。

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

代码

#define Fail print(-1), exit(0);
const int N = 1e5 + 7;
int n, p[N], s[N], f[N];
ll d[N], ans;
vi e[N];
map<ll, int> c;

void dfs(int x, int o) {
	ans += o;
	for (int y : e[x]) dfs(y, o + 1);
}

int main() {
	rd(n), rda(d, n);
	for (int i = 1; i <= n; i++) p[i] = i;
	sort(p + 1, p + n + 1, [&](int i, int j) { return d[i] < d[j]; });
	for (int i = 1; i <= n; i++) c[d[i]] = i, s[i] = 1;
	for (int i = n; i > 1; i--) {
		int u = p[i], fa;
		c.erase(d[u]);
		if (!(fa = c[d[u]-n+2*s[u]])) Fail;
		f[u] = fa, e[fa].pb(u), s[fa] += s[u];
	}
	dfs(p[1], 0);
	if (ans != d[p[1]]) Fail;
	for (int i = 1; i <= n; i++)
		if (f[i]) print(i, f[i]);
	return 0;
}