(u, v) 형식의 모서리 목록이 있고 이것이 나무를 나타낸다고 가정합니다. 각 모서리에 대해 입력에 제공된 것과 동일한 순서로 해당 모서리를 포함하는 고유한 경로의 총 수를 찾아야 합니다.
따라서 입력이 edge =[[0, 1],[0, 2],[1, 3],[1, 4]]
와 같은 경우
그러면 출력은 [6, 4, 4, 4]가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
adj :=주어진 가장자리의 인접 목록
-
count :=빈 지도
-
dfs() 함수를 정의합니다. x가 걸립니다. 부모
-
개수[x] :=1
-
adj[x]의 각 nb에 대해 수행
-
nb가 부모와 같으면
-
루프에서 나오다
-
-
개수[x] :=개수[x] + dfs(nb, x)
-
-
반환 횟수[x]
-
주요 방법에서 다음을 수행하십시오 -
-
dfs(0, -1)
-
ans :=새 목록
-
모서리의 각 모서리(a, b)에 대해 수행
-
x :=count[a] 및 count[b]의 최소값
-
as
끝에 (x *(count[0] - x)) 삽입
-
-
반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from collections import defaultdict class Solution: def solve(self, edges): adj = defaultdict(list) for a, b in edges: adj[a].append(b) adj[b].append(a) count = defaultdict(int) def dfs(x, parent): count[x] = 1 for nb in adj[x]: if nb == parent: continue count[x] += dfs(nb, x) return count[x] dfs(0, -1) ans = [] for a, b in edges: x = min(count[a], count[b]) ans.append(x * (count[0] - x)) return ans ob = Solution() edges = [ [0, 1], [0, 2], [1, 3], [1, 4] ] print(ob.solve(edges))
입력
[ [0, 1], [0, 2], [1, 3], [1, 4] ]
출력
[6, 4, 4, 4]