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 Description
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.
Example 1:
Input: g_nodes = 4, g_from = [1, 1, 2], g_to = [2, 3, 4]
Output: 0
Explanation: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:
Input: g_nodes = 6, g_from = [1, 1, 1, 2, 3], g_to = [2, 3, 4, 5, 6]
Output: 4
Explanation: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:
Input: g_nodes = 5, g_from = [1, 1, 2, 2], g_to = [2, 3, 4, 5]
Output: 0
Explanation:☝️
- 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 🌳
input:
output: