FastPrep
Problem · Tree

TikTok: Secondary Influencers

Learn this problem
● MediumTiktokINTERNOA
See Tiktok hiring insights

Problem statement

TikTok's influencer network can be represented as a tree of g_nodes numbered from 1 to g_nodes. Each connection between influencers is represented by an edge in the tree, where the i-th edge connects the influencers g_from[i] and g_to[i].

Suppose the maximum distance, i.e., the number of connections between any two influencers, is mx. An influencer is considered primary if they lie on the simple path between two influencers u and v such that the distance between u and v is equal to mx. All other influencers are secondary.

Your task is to find the sum of indices of all the secondary influencers.

Function

getSecondaryInfluencerSum(g_nodes: int, g_from: int[], g_to: int[]) → long

Complete the function getSecondaryInfluencerSum in the editor.

getSecondaryInfluencerSum has the following parameters:

  1. int g_nodes: the number of influencers in the network.
  2. int g_from[g_edges]: one influencer in each connection.
  3. int g_to[g_edges]: the other influencer in each connection.

Returns

long int: the sum of indices of the secondary influencers.

Examples

Example 1

g_nodes = 4g_from = [1, 1, 2]g_to = [2, 3, 4]return = 0
Example 1 illustration
The maximum distance between any two influencers is 3, the pair (3, 4). All the influencers on the path 3 --> 1 --> 2 --> 4 are primary. Since no influencer is secondary, the answer is 0.

Example 2

g_nodes = 6g_from = [1, 1, 1, 2, 3]g_to = [2, 3, 4, 5, 6]return = 4
Example 2 illustration
The max distance between any two influencer is 4 for the pair (5, 6). The influeners on the path 5 -> 2 -> 1 -> 3 -> 6 are primary. The only secondary influencer is number 4 :)

Example 3

g_nodes = 5g_from = [1, 1, 2, 2]g_to = [2, 3, 4, 5]return = 0
Example 3 illustration
☝️

Constraints

  • 2 <= g_nodes <= 105
  • 1 <= g_from[i], g_to[i] <= g_nodes
  • g_edges = g_nodes - 1
  • It is guaranteed that the edges from a tree 🌳

    • More Tiktok problems

    drafts saved locally
    public long getSecondaryInfluencerSum(int g_nodes, int[] g_from, int[] g_to) {
  // write your code here
}
    g_nodes4
    g_from[1, 1, 2]
    g_to[2, 3, 4]
    expected0
    checking account