第十二届蓝桥杯省赛第一场C++AC组 「左海子右兄弟」

左孩子右兄弟 题目描述：

对于一棵多叉树，我们可以通过 “左孩子右兄弟” 表示法，将其转化成一棵二叉树。

如果我们认为每个结点的子结点是无序的，那么得到的二叉树可能不唯一。

换句话说，每个结点可以选任意子结点作为左孩子，并按任意顺序连接右兄弟。

给定一棵包含 N 个结点的多叉树，结点从 1 至 N 编号，其中 1 号结点是根，每个结点的父结点的编号比自己的编号小。

请你计算其通过 “左孩子右兄弟” 表示法转化成的二叉树，高度最高是多少。

注：只有根结点这一个结点的树高度为 00。

思路：

对于一个节点，我们肯定是要将最深的那个子节点放在最右边，剩下的子节点们，每个只能产生1的深度的贡献，如下：

所以，我们dfs返回以自己为根的最大深度，这样我们dfs(u)的时候先dfs每个字节点v，记录最大值maxn，以及子节点的数量size,那u的最大深度就是maxn + size

#include 
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
vector<int>tr[MAX];

int dfs(int u, int fa){
    if(tr[u].size() == 1 && u != 1)return 1;
    int maxn = 0;
    for(auto v : tr[u]){
        if(v == fa)continue;
        maxn = max(maxn, dfs(v, u));
    }
    return maxn + (int)tr[u].size() - 1;
}

void work(){
    cin >> n;
    if(n == 1){
        cout << 0 << endl;
        return;
    }
    for(int u = 2, v; u <= n; ++u){
        cin >> v;
        tr[u].push_back(v);
        tr[v].push_back(u);
    }
    cout << dfs(1, -1) << endl;
}


int main(){
    io;
    work();
    return 0;
}