[NC记录]AT4434 [ARC103D] Distance Sums
command_block
2021-04-30 14:54:12
**题意** ： 有一棵 $n$ 个点的树，每条边的长度均为 $1$。
给出 $N$ 个**互不相同**的数 $d_i$，表示树上的节点 $i$ 到其他所有点的距离和。
构造一棵符合要求的树，或指出无解。
$n\leq 10^5$ ，时限$\texttt{2s}$。
------------
转战 ARC。
先考虑给出一棵树如何计算 $d$。
可以换根 $\rm DP$ :
对于相邻的点 $u,v$ ，记 $siz[u\rightarrow v]$ 表示以 $u$ 为根时 $v$ 的子树大小。
考虑 $d_u-d_v$。对于 $siz[u\rightarrow v]$ 代表的点，到 $u$ 的距离比到 $v$ 的距离大 $1$，对于 $siz[v\rightarrow u]$ 代表的点 ，到 $u$ 的距离比到 $v$ 的距离小 $1$。
故有 ：
$$d_u-d_v=siz[u\rightarrow v]-siz[v\rightarrow u]=2siz[u\rightarrow v]-n$$
首先有结论 ： $d_u$ 最小的 $u$ 是整棵树的重心。
我们进一步研究 $d$ 的结构。
首先有经典的结论 ： $d_u$ 最小的 $u$ 是重心。
若以重心为根，节点 $fa$ 为节点 $u$ 的父亲。观察式子 ：
$$d_{fa}=d_u+2siz[fa\rightarrow u]-n$$
根据重心的性质， $siz[fa\rightarrow u]\leq n/2$ ，故 $d_{fa}\geq d_u$。
也就是说，以重心为根时， $d$ 由浅到深单调不降。
回到本题。
我们将 $d$ 从大到小排序，这样父亲一定在儿子后面。
按照 $d$ 从大到小的排序考虑各个点。这时该点的子孙都已经被考虑过了，所以该点的子树大小是确定的。
根据子树大小 $siz[fa\rightarrow u]$ 和 $d_u$ ，就能得到 $d_{fa}$。
本题保证了 $d$ 互不相同，于是直接（二分）查找符合条件的点即可。若找不到，则无解。
最后，我们上述构造只是保证了所有的 $d_u-d_{fa}$ 是合法的。所以还需任选一个 $d_u$ 验证是否合法。
复杂度 $O(n\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 100500
using namespace std;
struct Data2{int u,v;}ans[MaxN];
struct Data{ll x;int p;}b[MaxN];
bool cmp(const Data &A,const Data &B)
{return A.x<B.x;}
int n,siz[MaxN];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%lld",&b[i].x);
b[i].p=i;siz[i]=1;
}sort(b+1,b+n+1,cmp);
for (int i=n;i>1;i--){
ll td=b[i].x+2*siz[i]-n;
int p=lower_bound(b+1,b+n+1,(Data){td,0},cmp)-b;
if (p>=i||b[p].x!=td){puts("-1");return 0;}
ans[i]=(Data2){b[i].p,b[p].p};
siz[p]+=siz[i];
}
ll td=0;
for (int i=1;i<=n;i++)td+=siz[i];
if (td-n!=b[1].x){puts("-1");return 0;}
for (int i=n;i>1;i--)
printf("%d %d\n",ans[i].u,ans[i].v);
return 0;
}
```