CF746G 题解

闲话:2100的紫? NOIP 集训,Smeow 讲图论,这是其中一个我觉得很妙的题,所以题解总结一下 qwq。没怎么写过题解,思路混乱请见谅。

传送门

题意:给一棵一共有 $n$ 个点的树,$t+1$ 层。第一层只有一个根节点,给出每层的节点数。已知有 $k$ 个叶子,求任意一种树的构造方案。

Solution:首先考虑构造一条链,满足题目 $t+1$ 层的要求,然后往上面挂节点。如果需要叶子,那么直接挂到这一层链上的节点,否则挂到上一层对应的节点(也是叶子),这样不会增加叶子数量,因为挂到上一层的叶子上会让叶子数量减 $1$,再加上新的,叶子数不变。记得判断无解,节点数不够叶子或有多余非叶子节点,具体实现看代码。第二种思路,先尽可能多地放叶子,再进行调整,把原来连在链上的点放到对应上层叶子减少叶子数,两种思路本质差别不大,这里只提供第一种实现。

const int N=2e5+10;
int n,t,k;
int a[N],fa[N];
vector<int> v[N];//v[i][j]表示第 i 层第 j 个点(设首都是第 0 层)
int cnt=1,notleaf;//记得加上首都
int main(){
read(n,t,k);
for(int i=1;i<=t;++i) read(a[i]);
if(n-t<k||a[t]>k) return puts("-1"),0;
//特判,如果节点数量不够叶子或者最后一层节点数大于叶子数,直接-1
v[0].push_back(1);//先把首都加进去
for(int i=1;i<=t;++i) for(int j=1;j<=a[i];++j) v[i].push_back(++cnt);//给节点编号
for(int i=1;i<=t;++i) fa[v[i][0]]=v[i-1][0];//先构造链
for(int i=1;i<a[1];++i) fa[v[1][i]]=1;//第 1 层不用看,一定连到首都
notleaf=n-t-k;//记录的是非叶子节点数量
for(int i=2;i<=t;++i)
for(int j=1;j<a[i];++j){
if(notleaf>0&&j<a[i-1]) fa[v[i][j]]=v[i-1][j],notleaf--;
//如果不需要叶子,挂到对应的上一层节点,不增加叶子数量
else fa[v[i][j]]=v[i-1][0];//需要叶子,直接挂到上一层链上的节点即可
}
if(notleaf>0) puts("-1");//如果还有剩余,无解
else{
printf("%d\n",n);
for(int i=2;i<=n;++i) printf("%d %d\n",fa[i],i);//按要求输出边
}
return 0;
}

完结撒花!