P11242 碧树题解

· · 题解

P11242 碧树题解

前置芝士:树的深度和层数 如图

（画的太丑还请见谅）

正文

对于一棵有向树，除最深层结点和根节点以外的所有点均 需要一个兄弟结点连接上下层，否则其无法作为叶子结 点

也就是说至少需要一个长度为最大深度-1 （因为最大深度的点实际上是叶子，它是接在比它小一个深度 的结点上的） 的链，在这个链的基础上加的点都是叶子结点。

因此我们只要知道叶子最大深度为多少，然后先构建一个最大深度-1的链，再在这个链的结点上面加叶子即可构造出的树即为结点最少的树\ （以样例一为例）如图\ （需注意题中根节点不计为结点） \ 因此易得答案ans=k-1+maxn（最大深度-1加上叶子数）

代码

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int k,maxn;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>k;
    int x; 
    for(int i=1;i<=k;i++){
        cin>>x;
        maxn=max(x,maxn);//只要记录叶子的最大深度最后减去1即为链的深度 
    }
    cout<<maxn+k-1;
    return 0; 
}

PS：蒟蒻第一篇题解写的不好求见谅