Pythonのツリーで、距離が正確にkである頂点の個別のペアの数を見つけます

整数kがあり、n個のノードを持つツリーがあるとすると、正確なk距離を持つ頂点の個別のペアの数を数える必要があります。

したがって、入力がk=2のような場合

その場合、出力は4になります

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

• N：=5005

• グラフ：=サイズNの隣接リスト

• Vertex_count：=サイズ505x5005の2次元行列

• res：=0

• 関数insert_edge（）を定義します。これにはx、yが必要です

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

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

• 関数dfs（）を定義します。これにはv、親が必要です

• Vertex_count [v、0]：=1

• グラフ[v]の各iについて、実行

  • 私が親と同じでない場合は、

    • dfs（i、v）

    • 1からk+1の範囲のjの場合、実行

      • res：=res + Vertex_count [i、j --1] * Vertex_count [v、k --j]

    • 1からk+1の範囲のjの場合、実行

      • 頂点カウント[v、j]：=頂点カウント[v、j] +頂点カウント[i、j-1]

例

理解を深めるために、次の実装を見てみましょう-

N = 5005
graph = [[] for i in range(N)]
vertex_count = [[0 for i in range(505)] for i in range(N)]
res = 0
def insert_edge(x, y):
   graph[x].append(y)
   graph[y].append(x)
def dfs(v, parent):
   global res
   vertex_count[v][0] = 1
   for i in graph[v]:
      if (i != parent):
         dfs(i, v)
         for j in range(1, k + 1):
            res += vertex_count[i][j - 1] * vertex_count[v][k - j]
         for j in range(1, k + 1):
            vertex_count[v][j] += vertex_count[i][j - 1]
k = 2
insert_edge(1, 2)
insert_edge(2, 3)
insert_edge(3, 4)
insert_edge(2, 5)
dfs(1, 0)
print(res)

k = 2
insert_edge(1, 2)
insert_edge(2, 3)
insert_edge(3, 4)
insert_edge(2, 5)

4