TikTok: Secondary Influencers
Learn this problem
TiktokINTERNOAProblem 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:
int g_nodes: the number of influencers in the network.int g_from[g_edges]: one influencer in each connection.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
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
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
☝️
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 🌳