luogu#P10678. 『STA - R6』月
『STA - R6』月
题目背景
题目描述
对于一棵有 个节点的树 ,定义其直径 为任意两个节点之间距离的最大值。
给定正整数 和每个点 的度数 ,你需要构造一棵树 ,同时最小化 。
保证至少存在一棵符合要求的树,若存在多个符合要求的答案,输出任意一个即可。
输入格式
本题单个测试点内含有多组测试数据。
第一行一个正整数 ,代表测试数据组数。
对于每组测试数据,
-
第一行一个正整数 。
-
第二行 个正整数,第 个正整数表示点 的度数 。
输出格式
对于每组测试数据,输出 行,每行两个正整数 ,表示构造出的树的边集。
4
2
1 1
3
1 1 2
5
1 1 2 2 2
7
1 3 2 3 1 1 1
2 1
1 3
3 2
5 4
4 2
3 1
3 5
4 2
3 2
1 2
5 4
6 4
7 3
提示
【样例解释】
对于最后一组数据,所构造出的树如下图:
其直径等于点 之间或点 之间的距离,为 。可以证明,不存在满足条件的直径小于 的树。
【数据范围】
本题采用捆绑测试。
对于 的数据:
- ;
- ;
- ;
- ;
- 保证至少存在一个合法的解。
具体部分分分配如下:
Subtask 编号 | 数据范围 | 分值 |
---|---|---|
1 | ||
2 | ||
3 | 中只含有两种本质不同的元素 | |
4 | 无特殊限制 |