统计最高分的节点数目 图解题解

这道题到底在问什么

输入

parents=[-1,2,0,2,0]

输出

3

输入

parents=[-1,2,0]

输出

2

先想最直接的笨办法

五个节点的子树大小都到手了:节点 0 是 5,节点 2 是 3,节点 1、节点 3、节点 4 各是 1。有了这张表,接下来就能一个一个删节点、算分数。约定好评分口径:删掉节点后剩下的每一块大小相乘。下面按节点编号 0 到 4 的顺序逐个算。（动画第 10 步）

最优解：一步一步想明白

1. 3记牢这一句:分数等于删掉该节点后各块大小的乘积。块分两种,一种是它的每棵子树,大小直接是子树 size;另一种是上方剩下的那块,大小是 n 减去它的子树大小。下面先把五个节点的子树大小求出来。
2. 4n = 5 · 目标:每个节点的分数这就是要处理的树。节点 0 是根,它有两个孩子节点 2 和节点 4;节点 2 底下又挂着节点 1 和节点 3;节点 4、节点 1、节点 3 都是叶子。一共 5 个节点。第一步不急着算分,先自底向上把每个节点的子树大小求出来,后面算分全靠它。
3. 5节点 1 子树大小 = 1先看最底下的叶子节点 1。它没有孩子,子树里就它自己一个,子树大小是 1。叶子的子树大小永远是 1,这是递归的底。
4. 6节点 3 子树大小 = 1同样,叶子节点 3 也没有孩子,子树大小是 1。它和节点 1 是节点 2 的两个孩子。
5. 7节点 2 子树大小 = 3轮到节点 2。它的子树包含它自己,加上左孩子节点 1 的子树 1 个、右孩子节点 3 的子树 1 个,所以子树大小是 1 加 1 加 1,等于 3。这三个绿色节点就是节点 2 那一整棵子树。
6. 8节点 4 子树大小 = 1再看叶子节点 4,它挂在根节点 0 下面,没有孩子,子树大小是 1。
7. 9节点 0 子树大小 = 5最后是根节点 0。它的子树就是整棵树,自己 1 个,加上节点 2 那棵 3 个、节点 4 那棵 1 个,子树大小是 1 加 3 加 1,等于 5,正好是全部节点数。
8. 10五个 size 已求出五个节点的子树大小都到手了:节点 0 是 5,节点 2 是 3,节点 1、节点 3、节点 4 各是 1。有了这张表,接下来就能一个一个删节点、算分数。约定好评分口径:删掉节点后剩下的每一块大小相乘。下面按节点编号 0 到 4 的顺序逐个算。
9. 11正在删:节点 0第一个算根节点 0。把节点 0 和它的两条边删掉,树就断成两块,正好是它的两棵子树:节点 2 领头那棵 3 个节点,节点 4 单独那棵 1 个节点。根节点比较特殊,它上面没有别的节点,所以没有上方那一块,下一帧确认一下。
10. 12分数 = 3 × 1 = 3节点 0 的分数就是两棵子树大小相乘:3 乘 1 等于 3。它是第一个算的,先把当前最高分记成 3,达到最高分的节点数记成 1。别急着下结论,后面还有四个节点。
11. 13正在删:节点 1轮到叶子节点 1。它没有孩子,删掉它以后,剩下的 4 个节点还连成一整块,不会散开。所以只裂出上方这一块,大小下一帧算。
12. 14上方块 = 5 - 1 = 4再看上方那一块。它等于总数 n 减去节点 1 的子树大小,也就是 5 减 1 等于 4。这 4 个节点是删点之后除它子树以外剩下的全部,连在一起算一块。叶子就这一块。
13. 15分数 = 4 = 4节点 1 的分数是各块大小相乘:4 = 4。这个 4 比之前的最高分 3 还大,所以刷新最高分为 4,并把达到最高分的节点数重新记成 1。注意叶子删完只剩一块,分数就等于那块的大小 4。
14. 16正在删:节点 2轮到节点 2。删掉它和连着的边,先看它自己的子树:左孩子节点 1 那棵大小 1,右孩子节点 3 那棵大小 1。除了这两棵,它上面还连着一块,下一帧单独算。
15. 17上方块 = 5 - 3 = 2再看上方那一块。它等于总数 n 减去节点 2 的子树大小,也就是 5 减 3 等于 2。这 2 个节点是删点之后除它子树以外剩下的全部,连在一起算一块。加上前面两棵子树,节点 2 删完一共 3 块。
16. 18分数 = 1 × 1 × 2 = 2节点 2 的分数是 1 × 1 × 2 = 2。它比当前最高分 4 小,不是我们要的,最高分和计数都保持不变。可以看到节点 2 虽然裂成三块,乘积却只有 2,反而不占优。
17. 19正在删:节点 3轮到叶子节点 3。它没有孩子,删掉它以后,剩下的 4 个节点还连成一整块,不会散开。所以只裂出上方这一块,大小下一帧算。
18. 20上方块 = 5 - 1 = 4再看上方那一块。它等于总数 n 减去节点 3 的子树大小,也就是 5 减 1 等于 4。这 4 个节点是删点之后除它子树以外剩下的全部,连在一起算一块。叶子就这一块。
19. 21分数 = 4 = 4节点 3 的分数是 4 = 4。它正好等于当前最高分 4,不刷新最高分,但达到最高分的节点数加一,变成 2。又一个叶子拿到 4 分。
20. 22正在删:节点 4轮到叶子节点 4。它没有孩子,删掉它以后,剩下的 4 个节点还连成一整块,不会散开。所以只裂出上方这一块,大小下一帧算。
21. 23上方块 = 5 - 1 = 4再看上方那一块。它等于总数 n 减去节点 4 的子树大小,也就是 5 减 1 等于 4。这 4 个节点是删点之后除它子树以外剩下的全部,连在一起算一块。叶子就这一块。
22. 24分数 = 4 = 4节点 4 的分数是 4 = 4。它正好等于当前最高分 4,不刷新最高分,但达到最高分的节点数加一,变成 3。又一个叶子拿到 4 分。
23. 25节点 1 / 3 / 4 都是 4停下来看个规律。三个叶子节点 1、3、4 的分数都是 4,也就是 n 减 1。原因很直接:删掉一个叶子,剩下的节点全都还连成一整块,大小就是 n 减 1,而这块又是唯一一块,乘积就是它自己。所以在很多树里,叶子的分数天然不低,常常就是那个最高分。
24. 26答案 = 3五个节点全算完了。分数依次是节点 0 得 3、节点 1 得 4、节点 2 得 2、节点 3 得 4、节点 4 得 4。最高分是 4,达到它的有节点 1、节点 3、节点 4 三个,所以答案是 3。整个过程就是一趟后序求子树大小,再对每个节点把各块大小相乘比一比,时间是线性的。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
import sys
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def countHighestScoreNodes(self, parents: List[int]) -> int:
        # 链形树递归深度可达 n(最多十万),先调高递归上限,避免 RecursionError
        sys.setrecursionlimit(200005)
        def dfs(i: int, fa: int):
            cnt = score = 1
            for j in g[i]:
                if j != fa:
                    t = dfs(j, i)
                    score *= t
                    cnt += t
            if n - cnt:
                score *= n - cnt
            nonlocal ans, mx
            if mx < score:
                mx = score
                ans = 1
            elif mx == score:
                ans += 1
            return cnt

        n = len(parents)
        g = [[] for _ in range(n)]
        for i in range(1, n):
            g[parents[i]].append(i)
        ans = mx = 0
        dfs(0, -1)
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int countHighestScoreNodes(vector<int>& parents) {
        int n = parents.size();
        vector<int> g[n];
        for (int i = 1; i < n; ++i) {
            g[parents[i]].push_back(i);
        }
        int ans = 0;
        long long mx = 0;
        function<int(int, int)> dfs = [&](int i, int fa) {
            long long score = 1;
            int cnt = 1;
            for (int j : g[i]) {
                if (j != fa) {
                    int t = dfs(j, i);
                    cnt += t;
                    score *= t;
                }
            }
            if (n - cnt) {
                score *= n - cnt;
            }
            if (mx < score) {
                mx = score;
                ans = 1;
            } else if (mx == score) {
                ++ans;
            }
            return cnt;
        };
        dfs(0, -1);
        return ans;
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private List<Integer>[] g;
    private int ans;
    private long mx;
    private int n;

    public int countHighestScoreNodes(int[] parents) {
        n = parents.length;
        g = new List[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int i = 1; i < n; ++i) {
            g[parents[i]].add(i);
        }
        // 链形树递归深度可达 n(最多十万),默认线程栈会溢出;
        // 把 DFS 放进一个更大栈的线程里跑,规避 StackOverflowError。
        Thread worker = new Thread(null, () -> dfs(0, -1), "dfs", 1 << 26);
        worker.start();
        try {
            worker.join();
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
        return ans;
    }

    private int dfs(int i, int fa) {
        int cnt = 1;
        long score = 1;
        for (int j : g[i]) {
            if (j != fa) {
                int t = dfs(j, i);
                cnt += t;
                score *= t;
            }
        }
        if (n - cnt > 0) {
            score *= n - cnt;
        }
        if (mx < score) {
            mx = score;
            ans = 1;
        } else if (mx == score) {
            ++ans;
        }
        return cnt;
    }
}

复杂度

面试官可能追问