2049. Count the number of nodes with the highest score: graph + DFS application

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Topic describes

This is 2049 on LeetCode. Counting the number of nodes with the highest score is medium difficulty.

Tag: “Graph theory”, “linear DP”

You are given a binary tree with root node 000, which has a total of NNN nodes numbered from 000 to N − 1n-1n −1.

Parentsparentsparents is the tree, where parents[I]parents[I]parents[I]parents[I] is the parent of node III. Since node 000 is the root, parents[0]==−1parents[0] == -1parents[0]==−1.

The size of a subtree is the number of nodes in the subtree. Each node has a score associated with it. The score of a node is obtained by deleting the node and all edges connected to it. The remaining part is a number of non-empty subtrees. The score of this node is the product of the sizes of all these subtrees.

Return the number of nodes with the highest score.

Example 1:

Parents = [-1,2,0,2,0] parents = [-1,2,0] parents = [-1,2,0] Parents = [-1,2,0] Parents = [-1,2,0] 4 = 4 - the score of node 4 is: 4 = 4 the highest score is 4, with three nodes scoring 4 (nodes 1,3 and 4 respectively).Copy the code

Example 2:

Input: parents = [-1,2,0] input: parents = [-1,2,0] output: 2 1 * 1 = 1 The highest score is 2, and there are two nodes with scores of 2 (nodes 0 and 1 respectively).Copy the code

Tip:

• 
  $n == parents.length$
• 
  $2 <= n <= 10^5$
• 
  $parents[0] == -1$
• For the I! =0i ! = 0i! = 0, 0 < = parents [I] < = n < = parents – 10 [I] < < = = n – 10 parents [I] < = n – 1
• Parentsparentsparents indicates a binary tree.

Built figure + DFS

For the sake of generality, we assume that the tree is a multi-fork tree.

Since the given parents array only allows us to quickly find the parent of a node, to facilitate traversing the whole tree, we first use the “adjacency list” to build the graph (tree).

Then DFS is used to preprocess the f array, where F [I]f[I] represents the number of nodes contained in the subtree with node III as the root node.

Consider how to calculate “the number of remaining connected blocks and the number of nodes of each connected block after deleting a node XXX”, and discuss in different cases according to whether node XXX is the root node:

• If XXX is the root node, the number of deleted connected blocks is “the number of outgoing edges of XXX”. Assuming that there are KKK outgoing edges, according to the definition of the question, the corresponding size is the product of the number of nodes of each connected block:

• If XXX is not the root node, the number of deleted connected blocks is “the number of outgoing edges of XXX + 111”, where 111 refers to “the whole connected block where the parent node of XXX is located”.

  It is assumed that node XXX has KKK outsides. According to the definition of the title, the corresponding size is “(product of the number of nodes of each connected block) ×\times× (size of the overall connected block where the parent of XXX node is located)”, and “size of the overall connected block where the parent of XXX node is located”, F [root]− F [u]= N − F [u]f[root] -f [u]= N-f [U]f[root]− F [u]= N − F [u], which means subtracting the subtree with node XXX as the root from the original tree. That is, the final size is:

Code:

class Solution {
    static int N = 100010, M = N * 2;
    static int[] he = new int[N], e = new int[M], ne = new int[M];
    static int[] f = new int[N];
    int idx;
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx++;
    }
    public int countHighestScoreNodes(int[] parents) {
        Arrays.fill(he, -1);
        int n = parents.length;
        for (int i = 1; i < n; i++) add(parents[i], i);
        dfs(0);
        long max = 0;
        int ans = 0;
        for (int x = 0; x < n; x++) {
            long cur = 1;
            for (inti = he[x]; i ! = -1; i = ne[i]) cur *= f[e[i]];
            if(x ! =0) cur *= n - f[x];
            if (cur > max) {
                max = cur; ans = 1;
            } else if(cur == max) { ans++; }}return ans;
    }
    int dfs(int u) {
        int ans = 1;
        for (inti = he[u]; i ! = -1; i = ne[i]) ans += dfs(e[i]);
        f[u] = ans;
        returnans; }}Copy the code

• Time complexity: The complexity of the diagram is
  $O(n)$; throughDFSpretreatmentfThe array complexity is
  $O(n + m)$, including
  $m$Is the number of edges. For this case (binary tree), the order of magnitude is the same, soDFSThe complexity of preprocessing is
  $O(n)$; Simulation deletes any point and calculates the complexity of the answer as
  $O(n + m)$In this case, the order of magnitude is
  $O(n)$. The overall complexity is
  $O(n)$
• Space complexity: O(n)O(n)O(n)

The last

This is the No.2049 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.