0 写在之前

这几天写的题目并不算少

然而这道题是唯一一个看过去傻了的题目…

应该以前听过，题面看着眼熟

可是死活不会做…

1 思路

基本上可以明确是到构造题

这里依赖两个性质：

树的中心的 $D$ 值是最小的

$$ D(fa) = D(x) – n + 2 \times size[i] $$

这个就是标准的树和树的重心的性质

可以推出来如果以重心做根，那么 $D$ 越大越在下面

所以尝试生成一颗以重心为根的树就行了

然后我发现我不会判否

结果发现最后生成出来树判断一次就行了…

2 实现

读入 $D$ 排序

从大到小依此根据上面的式子找父亲

最后判断一下是否正确就可以了

3 Code

// User: woshiluo
// Email: [email protected]
// Problem link: https://atcoder.jp/contests/arc103/tasks/arc103_d
// Comment: 
// Why the problem id is 'F', but the link is 'arc103_d'
// Interesting

#include <cstdio>
#include <cstdlib>

#include <map>
#include <algorithm>

const int N = 1e5 + 1e3;

int n;
int size[N], father[N];

struct node{
	int id;
	long long d;
} a[N];

std::map<long long, int> mp;

void wrong() {
	printf( "-1\n" );
	exit(0);
}
bool cmp( node _a, node _b ) { return _a.d < _b.d; }

int main() {
#ifdef woshiluo
	freopen( "F.in", "r", stdin );
	freopen( "F.out", "w", stdout );
#endif
	scanf( "%d", &n );
	for( int i = 1; i <= n; i ++ ) {
		scanf( "%lld", &a[i].d );
		a[i].id = i;
		size[i] = 1;
		mp[ a[i].d ] = i;
	}
	std::sort( a + 1, a + n + 1, cmp );
	int rt_d, rt;
	rt = a[1].id; rt_d = a[1].d;
	for( int i = n; i > 1; i -- ) {
		int fa = mp[ a[i].d + 2LL * size[ a[i].id ] - n ];
		if( fa == 0 ) {
			wrong();
			return 0;
		} 
		size[fa] += size[ a[i].id ];
		father[ a[i].id ] = fa;
	}
	for( int i = 1; i <= n; i ++ ) {
		if( i == rt ) 
			continue;
		 rt_d -= size[i];
	}
	if( rt_d != 0 ) 
		wrong();

	for( int i = 1; i <= n; i ++ ) {
		if( i == rt ) 
			continue;
		printf( "%d %d\n", father[i], i );
	}
}