Problem Brief

TikTok: Secondary Influencers

INTERNOA

See Tiktok online assessment and hiring insights

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.

1Example 1

Input

g_nodes = 4, g_from = [1, 1, 2], g_to = [2, 3, 4]

Output

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.

2Example 2

Input

g_nodes = 6, g_from = [1, 1, 1, 2, 3], g_to = [2, 3, 4, 5, 6]

Output

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 :)

3Example 3

Input

g_nodes = 5, g_from = [1, 1, 2, 2], g_to = [2, 3, 4, 5]

Output

Explanation

☝️

Constraints

Limits and guarantees your solution can rely on.

2 <= g_nodes <= 10⁵

1 <= g_from[i], g_to[i] <= g_nodes

g_edges = g_nodes - 1

It is guaranteed that the edges from a tree 🌳