C ++中树的距离总和

假设我们有一棵无向的，连接的树，其中有N个节点。这些标记为0 ... N-1，给出了N-1边。第i条边将节点edge [i] [0]和edge [i] [1]连接在一起。我们必须找到一个列表，其中ans [i]是节点i与所有其他节点之间的距离之和。

因此，如果输入像N = 6并且edges = [[(0,1)，(0,2)，(2,3)，(2,4)，(2,5)]，那么输出将为[8,12,6,10,10,10]

为了解决这个问题，我们将遵循以下步骤-

• 定义一个函数dfs1()，它将使用node，parent，

• 子：= graph [node，i]

• 如果孩子不等于父母，那么-

• dfs1（子节点）

• cnt [node]：= cnt [node] + cnt [child]

• ans [node]：= ans [node] + cnt [child] + ans [child]

• 对于初始化i：= 0，当i <graph [node]的大小时，更新（将i增加1），执行-

• 定义一个函数dfs2()，它将使用node，parent，

• 子：= graph [node，i]

• 如果孩子不等于父母，那么-

• ans [child]：= ans [node]-cnt [child] + N-cnt [child]

• dfs2（子节点

• 对于初始化i：= 0，当i <graph [node]的大小时，更新（将i增加1），执行-

• 定义一个数组ans

• 定义一个数组cnt

• 定义具有10005行的数组图

• 从主要方法中，执行以下操作-

• N个：= N

• ans：=定义大小为N的数组

• cnt：=定义一个大小为N的数组，并用1填充

• n：=边的大小

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• u：= edges [i，0]

• v：= edges [i，1]

• 在图形的末尾插入v [u]

• 在图形[v]的末尾插入u

• dfs1(0,-1)

• dfs2(0,-1)

• 返回ans

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0;
   i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   void dfs1(int node, int parent) {
      for (int i = 0; i < graph[node].size(); i++) {
         int child = graph[node][i];
         if (child != parent) {
            dfs1(child, node);
            cnt[node] += cnt[child];
            ans[node] += cnt[child] + ans[child];
         }
      }    
   }
   void dfs2(int node, int parent) {
      for (int i = 0; i < graph[node].size(); i++) {
         int child = graph[node][i];
         if (child != parent) {
            ans[child] = ans[node] - cnt[child] + N - cnt[child];
            dfs2(child, node);
         }
      }
   }
   vector<int> ans;
   vector<int> cnt;
   vector<int> graph[10005];
   int N;
   vector<int> sumOfDistancesInTree(int N, vector<vector<int> >& edges) {
      this->N = N;
      ans = vector<int>(N);
      cnt = vector<int>(N, 1);
      int n = edges.size();
      for (int i = 0; i < n; i++) {
         int u = edges[i][0];
         int v = edges[i][1];
         graph[u].push_back(v);
         graph[v].push_back(u);
      }
      dfs1(0, -1);
      dfs2(0, -1);
      return ans;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1},{0,2},{2,3},{2,4},{2,5}}; print_vector(ob.sumOfDistancesInTree(6,    v));
}

输入值

{{0,1},{0,2},{2,3},{2,4},{2,5}}

输出结果

[8, 12, 6, 10, 10, 10, ]