C++でのツリーの距離の合計

N個のノードが存在する1つの無向の接続されたツリーがあるとします。これらは0...N-1としてラベル付けされ、N-1エッジが与えられます。 i番目のエッジは、ノードedges[i][0]とedges[i][1]を接続します。 ans[i]がノードiと他のすべてのノード間の距離の合計であるリストを見つける必要があります。

したがって、入力がN =6で、エッジ=[（0,1）、（0,2）、（2,3）、（2,4）、（2,5）]の場合、出力は次のようになります。 [8,12,6,10,10,10]

これを解決するには、次の手順に従います-

• 関数dfs1（）を定義します。これは、ノード、親、

  を取ります。

  • 初期化i：=0の場合、i <グラフ[ノード]のサイズの場合、更新（iを1増やします）、実行-

    • 子：=グラフ[ノード、i]

    • 子が親と等しくない場合、-

      • dfs1（子、ノード）

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

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

• 関数dfs2（）を定義します。これは、ノード、親、

  を取ります。

  • 初期化i：=0の場合、i <グラフ[ノード]のサイズの場合、更新（iを1増やします）、do-

    • 子：=グラフ[ノード、i]

    • 子が親と等しくない場合、-

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

      • dfs2（子、ノード

• 配列を定義します

• 配列cntを定義する

• 10005行の配列グラフを定義する

• メインの方法から、次のようにします-

• こののN：=N

• ans：=サイズNの配列を定義する

• cnt：=サイズNの配列を定義し、これを1で埋めます

• n：=エッジのサイズ

• 初期化i：=0の場合、i

  • u：=エッジ[i、0]

  • v：=エッジ[i、1]

  • グラフの最後にvを挿入します[u]

  • グラフの最後にuを挿入します[v]

• 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, ]