题意:有一棵树,对于每个点$i$,给出了它到其他点的距离和$i$,现在要还原这棵树,保证$d_i$两两不同
一个点从$u$移到相邻节点$v$时,若删掉$(u,v)$后$u$这边的连通块大小为$siz_u$,$v$这边的连通块大小为$siz_v$,那么$d_v=d_u-siz_v+siz_u$
首先,有最大$d_x$的$x$是叶子,并且我们知道它的父亲的$d$为$d_x-(n-1)+1$
所以考虑按$d$从大到小的顺序确定每个点$x$的父亲:这个点的$d$必须是$d_x-(n-siz_x)+siz_x$,因为题目保证了$d_i$两两不同,所以这个过程容易实现,如果中间找不到对应的$d$或者$siz_x=\frac n2$就无解
最后还得判一下造出来的树是否真的符合要求,因为这种构造方式没有保证根的$d$是对的,一旦根的$d$是对的,那么整棵树就是满足要求的了
#include<stdio.h> #include<map> using namespace std; typedef long long ll; map<ll,int>p; map<ll,int>::iterator it; int fa[100010],siz[100010],a[100010],b[100010],h[100010],nex[200010],to[200010],M,n; void add(int a,int b){ M++; to[M]=b; nex[M]=h[a]; h[a]=M; } ll wd[100010],d[100010]; void dfs(int x,int dis){ siz[x]=1; d[1]+=dis; for(int i=h[x];i;i=nex[i]){ if(to[i]!=fa[x]){ fa[to[i]]=x; dfs(to[i],dis+1); siz[x]+=siz[to[i]]; } } } void dfs(int x){ for(int i=h[x];i;i=nex[i]){ if(to[i]!=fa[x]){ d[to[i]]=d[x]+n-siz[to[i]]*2; dfs(to[i]); } } } int get(int x){return fa[x]==x?x:(fa[x]=get(fa[x]));} int main(){ int i; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%lld",wd+i); p[wd[i]]=i; } for(i=1;i<=n;i++){ fa[i]=i; siz[i]=1; } it=p.end(); for(it--;it!=p.begin();it--){ if(n-siz[it->second]*2==0||!p.count(it->first-(n-siz[it->second]*2))){ puts("-1"); return 0; } M++; a[M]=it->second; b[M]=p[it->first-(n-siz[it->second]*2)]; siz[fa[a[M]]=get(b[M])]+=siz[a[M]]; } M=0; for(i=1;i<n;i++){ add(a[i],b[i]); add(b[i],a[i]); } fa[1]=0; dfs(1,0); dfs(1); for(i=1;i<=n;i++){ if(wd[i]!=d[i]){ puts("-1"); return 0; } } for(i=1;i<n;i++)printf("%d %d\n",a[i],b[i]); }