如何优化此 graph/tree 计算 C++ 中两个节点之间距离的问题？

Question

问题是找到树中两个节点之间的距离之和

输入：6 [[0,1],[0,2],[2,3],[2,4],[2,5]]

显示节点

输出：[8,12,6,10,10,10]

说明：树如上所示。

我们可以看到 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)

等于 1 + 1 + 2 + 2 + 2 = 8。

因此，答案[0] = 8，依此类推。

这是我的代码，我已经解决了，但这会导致 TLE，无法优化此解决方案

如何优化这个图形问题。

class Solution {
public:
    vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {
        vector<int> g[n];
        map<pair<int,int>,int> m;

        for(auto i:edges){
            g[i[0]].push_back(i[1]);
            g[i[1]].push_back(i[0]);
        }

        for(int i=0;i<n;i++){ 
            queue<int> q;
            q.push(i);
            vector<bool> vis(n,0);
            vis[i]=1;
            int incr=1;
            while(!q.empty()){
                int k=q.size();
                while(k--){
                    int t=q.front();q.pop();
                    for(int j=0;j<g[t].size();j++){
                        if(!vis[g[t][j]] && g[t][j]!=i){
                            m[{i,g[t][j]}]+=incr;
                            q.push(g[t][j]);
                            vis[g[t][j]]=1;
                        }
                    }
                }
                incr++;
            }
        }
        vector<int> res(n,0);
        for(auto i:m){
            res[i.first.first]+=i.second;
        }
        return res;
    }
};

Answer 1

正如我所看到的，您正在为每个节点使用 bfs 来查找距离。
你可以做的是使用动态规划
按照以下步骤解决问题

初始化一个向量dp，存储每个节点i到树的所有叶节点的距离之和。
初始化一个向量leaves，存储以1为根节点的节点i的子树中叶子节点的个数。
求节点i到所有叶节点的距离之和 i 的子树以 1 为根节点使用修改深度优先搜索算法。

Let node a be the parent of node i

leaves[a] += leaves[i] ;
dp[a] += dp[i] + leaves[i]

使用重新生根技术找到剩余的距离不在节点 i 的子树中的树叶。到计算这些距离，使用另一个改进的深度优先搜索 (DFS) 算法来查找和添加叶子的距离之和节点到节点 i.

Let a be the parent node and i be the child node, then
Let the number of leaf nodes outside the sub-tree i that are present in the sub-tree a be L

L = leaves[a] – leaves[i] ;
dp[i] += ( dp[a] – dp[i] ) + ( L – leaves[i] ) ;
leaves[i] += L ;

如何优化此 graph/tree 计算 C++ 中两个节点之间距离的问题？

How to optimize this graph/tree problem counting distance between two nodes in C++?

c++

caching

graph

dynamic-programming