1395. The Barycentre Of The Trees


Description

中文English
For a multi-branch tree, if there is a node R with R as the root, and the largest sub-tree of all its sub-trees has the least number of nodes, the node R is said to be the center of gravity of the tree.
Now give you a multi-branch tree with n nodes. Find the center of gravity of this tree. If there are multiple centers of gravity, return the one with the lowest number.
x[i], y[i] represents the two points of the i-th edge.

  • 2 <= n <= 10^5
  • 1 <= x[i], y[i] <= n

Example

Example 1:
Given x = `[1]`, y = `[2]`, return `1`.
Input:
[1]
[2]
Output:
1

Explanation:
Both 1 and 2 can be center of gravity, but the number of 1 is the smallest.
Example 2:
Given x = `[1,2,2]`, y = `[2,3,4]`, return `2`.
Input:
[1,2,2]
[2,3,4]
Output:
2

Explanation:
2 is the center of gravity.
Code(Language:C++)
class Solution {
public:
    /**
     * @param x: The vertexes of the edges
     * @param y: The vertexes of the edges
     * @return: Return the index of barycentre
     */
    void dfs(int x, int f, int &n, int &ansNode, int &ansSize, vector<int> &dp, vector<vector<int>> &tree) {
        dp[x] = 1;
        int maxSubtree = 0;
        for (int i = 0; i < tree[x].size(); i++) {
            int y = tree[x][i];
            if (y == f) {
                continue;
            }
            dfs(y, x, n, ansNode, ansSize, dp, tree);
            dp[x] += dp[y];
            maxSubtree = max(maxSubtree, dp[y]);
        }
        maxSubtree = max(maxSubtree, n - dp[x]);
        if (maxSubtree < ansSize || (maxSubtree == ansSize && x < ansNode)) {
            ansNode = x;
            ansSize = maxSubtree;
        }
    }
    int getBarycentre(vector<int> &x, vector<int> &y) {
        // Write your code here
        int n = x.size() + 1;
        vector<vector<int>> tree(n + 1);
        vector<int> dp(n + 1);
        for (int i = 0; i < x.size(); i++) {
            tree[x[i]].push_back(y[i]);
            tree[y[i]].push_back(x[i]);
        }
        int ansNode = 0;
        int ansSize = n + 1;
        dfs(1, 0, n, ansNode, ansSize, dp, tree);
        return ansNode;
    }
};

Comments

Post a Comment

Popular posts from this blog

Amazon OA 763. Partition Labels

class Solution { public:     vector<int> partitionLabels(string S) {         // 这是个好题         unordered_map<char, int> mp;         vector<int> res;         const int size = S.size();         if(size == 0){             return res;         }         for(int i = 0; i < size; i++){             mp[S[i]] = i;         }         int start = 0, end = 0;         for(int i = 0; i < size; i++){             end = max(end, mp[S[i]]);             if(i == end){                 res.push_back(i - start + 1);                 start = end + 1;     ...
Read more

1427. Split Array into Fibonacci Sequence

Description 中文 English Given a string S of digits, such as S = "123456579", we can split it into a Fibonacci-like sequence [123, 456, 579]. Formally, a Fibonacci-like sequence is a list F of non-negative integers such that: 0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type); F.length >= 3; and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2. Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself. Return any Fibonacci-like sequence split from S, or return [] if it cannot be done. 1 <= S.length <= 200 S contains only digits. Have you met this question in a real interview?    Yes Problem Correction Example Example 1: Input: "123456579" Output: [123,456,579] Example 2: Input: "11235813" Output: [1,1,2,3,5,8,13] Example 3: Input: "112358130" Output: [] Ex...
Read more