https://zeroplusfour.com/the-value-of-friendship-hackerrank-solution/

Here's how I did in all languages Java 8 , C++ , C , Python 3, Python 2.

jt_112's solution in Python3

parent={}
no_of_friends={}

def findparent(x):
    if parent[x] == x:
        return x
    parent[x] = findparent(parent[x])
    return parent[x]

def value (n):
    t1=n*(n+1)*(2*n+1)
    t1/=6
    t2=n*(n+1)
    t2/=2
    return t1-t2

    
def valueOfFriendsship(n,m, friendships):
    # Write your code here
    total, current, ans =0,0,0
    for i in range(1,n+1):
        parent[i] = i
        no_of_friends[i] = 1
    for i in range(m):
        u,v=friendships[i][0],friendships[i][1]
        pu,pv = findparent(u),findparent(v)
        if pu != pv:
                parent[pv] = pu
                no_of_friends[pu] += no_of_friends[pv]              
    p=[]
    for i in range(1,n+1):
        if(parent[i] == i):
            p.append(no_of_friends[i])
    p.sort(reverse=True)
    for i in range(len(p)):
        current+=(p[i]-1)
        ans +=value(p[i])+total*(p[i]-1)
        total+=(p[i] * (p[i]-1))
    ans+=((m-current)*total)
    return int(ans) 

how do i optimise this further only 1 test case passes with this one` def valueOfFriendsship(n, friendships): p=[i for i in range(1,n+1)] f=[0 for i in range(n)]

def findparent(n):
    if p[n-1]==n:
        return n
    else:
        return findparent(p[n-1])

def union(a,b):


    x=findparent(a)
    y=findparent(b)
    if x!=y:
        if f[a-1]>f[b-1]:
            p[b-1]=x
            a=f[a-1]+1
            for i in range(len(p)):
                if p[i]==x:
                    f[i]=a



        else:
            p[a-1]=y
            a=f[b-1]+1
            for i in range(len(p)):
                if p[i]==y:
                    f[i]=a


s=0
for i in friendships:
    union(i[0],i[1])
    s+=sum(f)
return s

`

This is a pretty simple combinatorics problem. HackerRank seems to base the difficulty levels of problems on the assumption that we don't know math.

I have solved it using dfs.
Good Problem by the way