Powered by:NEFU AB-IN

Link

3422. 左孩子右兄弟

• 题意

  第十二届蓝桥杯省赛第一场C++A/C组,第十二届蓝桥杯省赛第一场JAVAA/C组

  对于一棵多叉树，我们可以通过 “左孩子右兄弟” 表示法，将其转化成一棵二叉树。
  如果我们认为每个结点的子结点是无序的，那么得到的二叉树可能不唯一。
  换句话说，每个结点可以选任意子结点作为左孩子，并按任意顺序连接右兄弟。
  给定一棵包含 N 个结点的多叉树，结点从 1 至 N 编号，其中 1号结点是根，每个结点的父结点的编号比自己的编号小。
  请你计算其通过 “左孩子右兄弟” 表示法转化成的二叉树，高度最高是多少。
  注：只有根结点这一个结点的树高度为 0

• 思路

  树形dp裸题
  $$dp[u]=max(dp[u],dp[j]+num[u])$$
  num[u]表示的是以u为根节点的子节点个数
  当前树的高度等于它与其 子树高度 + 以这个节点为根的儿子结点数之和 取max

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2023-01-18 12:22:11
  * @FilePath: \Acwing\3422\3422.cpp
  * @LastEditTime: 2023-01-18 12:34:51
  */
  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #undef int
  
  #define SZ(X) ((int)(X).size())
  #define ALL(X) (X).begin(), (X).end()
  #define IOS                                                                                                            \
      ios::sync_with_stdio(false);                                                                                       \
      cin.tie(nullptr);                                                                                                  \
      cout.tie(nullptr)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  
  const int N = 1e5 + 10, INF = 0x3f3f3f3f;
  
  int n;
  vector<int> g[N];
  int dp[N], num[N];
  
  void dfs(int u)
  {
      for (auto v : g[u])
      {
          dfs(v);
          dp[u] = max(dp[u], dp[v] + num[u]);
      }
  }
  
  signed main()
  {
      IOS;
      cin >> n;
      for (int i = 2; i <= n; ++i)
      {
          int x;
          cin >> x;
          g[x].push_back(i);
          num[x]++;
      }
      dfs(1);
      cout << dp[1];
      return 0;
  }