题解 | #我们的距离#

方法零：用边的信息构造邻接矩阵，用floyd算法求节点间的最短距离，求和输出。这个方法用python实现超时，floyd算法对于边相对稀疏的树效率不高。（C++这么做可以通过，代码略）
方法一：遍历所有边，更新连通分量（Connected Component）和每个连通分量内的节点两两之间距离，最后求和得到答案输出

# class Point:
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 点的数量
# @param edge Point类一维数组 Point.x , Point.y 边所连接的两个点
# @return long长整型一维数组
#
class Solution:
    def solve(self , n , edge ):
        # write code here
        ran=range(n)
        dis=[[n]*n for i in ran]
        cur=0
        cc=[0]*n# Connected Component
        ccr=[]
        for i in ran:
            dis[i][i]=0
        for e in edge:
            x,y=e.x,e.y
            if cc[x-1]==0:# x not in cc
                if cc[y-1]==0:# y not in cc
                    cur+=1
                    ccr.append([x,y])
                    cc[x-1],cc[y-1]=cur,cur
                    dis[x-1][y-1]=1
                    dis[y-1][x-1]=1
                else:# y in cc
                    for a in ccr[cc[y-1]-1]:
                        dis[x-1][a-1]=dis[y-1][a-1]+1
                        dis[a-1][x-1]=dis[a-1][y-1]+1
                    cc[x-1]=cc[y-1]# connect x to cc of y
                    ccr[cc[y-1]-1].append(x)
            else:# x in cc
                if cc[y-1]==0:# y not in cc
                    for a in ccr[cc[x-1]-1]:
                        dis[y-1][a-1]=dis[x-1][a-1]+1
                        dis[a-1][y-1]=dis[a-1][x-1]+1
                    cc[y-1]=cc[x-1]# connect y to cc of x
                    ccr[cc[x-1]-1].append(y)
                else:# y in cc
                    # if x==y then we find a loop, but tree doesn't have loops
                    # so x=!y always true, merge cc
                    for a in ccr[cc[x-1]-1]:
                        for b in ccr[cc[y-1]-1]:
                            dis[a-1][b-1]=dis[a-1][x-1]+1+dis[y-1][b-1]
                            dis[b-1][a-1]=dis[b-1][y-1]+1+dis[x-1][a-1]
                    tmp=cc[x-1]
                    for b in ccr[cc[y-1]-1]:
                        cc[b-1]=tmp
                        ccr[tmp-1].append(b)
        f=[]
        for i in ran:
            f.append(sum(dis[i]))
        return f

方法二：DFS递归，保存中间值，参考这篇文章：hdu6446（dp+树上任意两点的最短距离）https://blog.csdn.net/rain722/article/details/75633721

# class Point:
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型 点的数量
# @param edge Point类一维数组 Point.x , Point.y 边所连接的两个点
# @return long长整型一维数组
#

class Solution:
    subtree=[]
    cnt=[]
    ans=[]
    def solve(self, n, edge):
        # write code here
        ran = range(n)
        Solution.subtree = [[]*n for i in ran]
        Solution.cnt = [[0]*n for i in ran]
        Solution.ans = [[0]*n for i in ran]
        for e in edge:
            Solution.subtree[e.x-1].append(e.y-1)
            Solution.subtree[e.y-1].append(e.x-1)
        for i in ran:
            self.dfs(i, i)
        return [Solution.ans[i][i] for i in ran]

    def dfs(self, cur, father):
        if Solution.cnt[cur][father] == 0:
            if cur!=father:
                Solution.cnt[cur][father] = 1
            for son in Solution.subtree[cur]:
                if son == father:
                    continue
                self.dfs(son, cur)
                Solution.cnt[cur][father] += Solution.cnt[son][cur]
                Solution.ans[cur][father] += Solution.ans[son][cur]
            if cur!=father:
                Solution.ans[cur][father] += Solution.cnt[cur][father]