打卡信奥刷题（3160）用C++实现信奥题 P7807 魔力滋生

P7807 魔力滋生

题目背景

Source：八仙敬酒，这是可以点的。

• 吕洞宾——醉酒提壶力千钧；
• 铁拐李——旋肘膝撞醉还真；
• 汉钟离——跌步抱坛兜心顶；
• 蓝采和——单提敬酒拦腰破；
• 张果老——醉酒抛杯踢连环；
• 曹国舅——仙人敬酒锁喉扣；
• 韩湘子——擒腕击胸醉吹箫；
• 何仙姑——弹腰献酒醉荡步。

题目描述

现有一个n nn个点的树T TT，满足任意一个结点的所连接的结点个数不超过2 22。

现在依次对结点u = 1 ∼ n u=1\sim nu=1∼n进行操作：

• 随机一个整数x ( ≥ k ) x(\ge k)x(≥k)；
• 新建x xx个结点，每个结点与u uu之间连一条边。

显然操作完成后仍是一棵树T ′ T'T′，其结点数为m = n + ∑ x m=n+\sum xm=n+∑x。

已知操作后的树T ′ T'T′及其结点数m mm，请还原原树T TT，若有多种方案，输出任意一组使得n \color{black}nn最大的。

值得注意的是，我们进行还原和输出时，只关心树的形状，而不关心结点的相对编号。

输入格式

第一行输入两个正整数m , k m,km,k，表示树T ′ T'T′的结点数、随机数x xx的下限。

第2 ∼ m 2\sim m2∼m行，每行输入两个正整数u , v u,vu,v，表示树T ′ T'T′中的一条边。

输出格式

第一行输出一个正整数n nn，表示构造出树T TT的结点数。

第2 ∼ n 2\sim n2∼n行，每行输出两个正整数u , v u,vu,v，表示树T TT中的一条边。

输出的u , v u,vu,v必须满足：1 ≤ u , v ≤ n 1\le u,v\le n1≤u,v≤n。

输入输出样例 #1

输入 #1

5 1 1 2 1 3 1 4 1 5

输出 #1

1

输入输出样例 #2

输入 #2

7 0 1 2 1 3 1 4 1 5 1 6 1 7

输出 #2

3 1 2 1 3

输入输出样例 #3

输入 #3

9 1 1 2 2 3 1 4 1 5 2 6 2 7 3 8 3 9

输出 #3

3 1 2 2 3

说明/提示

样例说明

样例# 1 \#1#1中，只有结点1 11可能在树T TT中：它对应的x xx是4 44。

样例# 2 \#2#2中，结点1 , 2 , 3 1,2,31,2,3在树T TT中：结点1 11对应的x xx是4 44，结点2 , 3 2,32,3对应的x xx是0 00。

样例# 3 \#3#3中，结点1 , 2 , 3 1,2,31,2,3在树T TT中：它们随机的x xx均为2 22。

样例# 3 \#3#3给出一张示意图，图中红色结点表示树T TT中的结点，图中所有结点都在树T ′ T'T′上。

数据范围

说明：Subtask4 为不计分 Hack 数据，只有通过全部的 Subtask1 ∼ 4 1\sim41∼4才算 AC。

对于100 % 100\%100%的数据：1 ≤ m ≤ 10 5 , k ∈ [ 0 , m ) 1\le m\le10^5,k\in[0,m)1≤m≤105,k∈[0,m)，数据输入保证有解。

后记

极光魔花好可爱∼ \sim∼

C++实现

#include<iostream>#include<algorithm>usingnamespacestd;constintN=1e5+10;structnode{intto,nxt,w;}e[N*2];inthead[N*2],tot;intans;intn,k;intf[N*2];voidadd(inta,intb,intc){e[++tot].to=b;e[tot].nxt=head[a];e[tot].w=c;head[a]=tot;}voiddfs(intu,intfa){for(inti=head[u];i;i=e[i].nxt){intv=e[i].to;intw=e[i].w;if(v==fa)continue;dfs(v,u);ans=max(ans,f[u]+f[v]+w);f[u]=max(f[u],f[v]+w);}}//求直径有两种方法，一种是这个dp,另外一个是两遍dfs,有兴趣的同学可以去找来看看。intmain(){cin>>n>>k;inta,b;for(inti=1;i<n;i++){scanf("%d%d",&a,&b);add(a,b,1);add(b,a,1);}dfs(1,-1);intcnt=ans+1;if(k==0){cout<<cnt<<endl;for(inti=1;i<cnt;i++){cout<<i<<" "<<i+1<<endl;}}else{cout<<max(1,cnt-2)<<endl;//有一点的坑的地方，当cnt-2小于等于零的情况是不存在的，所以要和1取最大值。for(inti=1;i<max(1,cnt-2);i++){cout<<i<<" "<<i+1<<endl;}}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容